D. Много игр
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Недавно вы получили редчайший билет в единственное казино в мире, в котором и правда можно что-то заработать, и вы хотите на полную воспользоваться этой возможностью.

Условия в этом казино следующие:

  • Всего в казино есть $$$n$$$ игр.
  • В каждую игру можно сыграть не более одного раза.
  • Каждая игра характеризуется двумя параметрами: $$$p_i$$$ ($$$1 \le p_i \le 100$$$) и $$$w_i$$$ — вероятность победы в игре в процентах и выигрыш за победу.
  • Если вы проиграете хоть в одной игре, в которую решите сыграть, то вы не получите вообще ничего (даже за выигранные игры).

Вам нужно заранее выбрать набор игр, в которые вы будете играть, таким образом, чтобы максимизировать математическое ожидание вашего выигрыша.

В данном случае, если вы выберите сыграть в игры с индексами $$$i_1 < i_2 < \ldots < i_k$$$, то вы выиграете во все из них с вероятностью $$$\prod\limits_{j=1}^k \frac{p_{i_j}}{100}$$$, и в таком случае ваш выигрыш будет равен $$$\sum\limits_{j=1}^k w_{i_j}$$$.

То есть математическое ожидание вашего выигрыша будет равно $$$\left(\prod\limits_{j=1}^k \frac{p_{i_j}}{100}\right) \cdot \left(\sum\limits_{j=1}^k w_{i_j}\right)$$$.

Чтобы не разориться, владельцы казино ограничили математическое ожидание выигрыша каждой отдельной игры. Таким образом, для всех $$$i$$$ ($$$1 \le i \le n$$$) выполнено $$$w_i \cdot p_i \le 2 \cdot 10^5$$$.

Ваша задача — найти максимальное математическое ожидание выигрыша, которое можно получить, выбрав какой-то набор игр в казино.

Входные данные

Первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество игр, в которые предлагается сыграть.

$$$i$$$-я из следующих $$$n$$$ строк содержит два целых числа $$$p_i$$$ и $$$w_i$$$ ($$$1 \leq p_i \leq 100$$$, $$$1 \leq w_i, p_i \cdot w_i \leq 2 \cdot 10^5$$$) — вероятность победы и размер выигрыша в $$$i$$$-й игре.

Выходные данные

Выведите одно число — максимальное математическое ожидание выигрыша в казино, которое можно получить, выбрав некоторое подмножество игр.

Ваш ответ будет засчитан, если относительная или абсолютная погрешность не будет превышать $$$10^{-6}$$$. Формально, если $$$a$$$ — ваш ответ, а $$$b$$$ — ответ жюри, то он будет засчитан, если $$$\frac{|a-b|}{\max(b, 1)} \le 10^{-6}$$$.

Примеры
Входные данные
3
80 80
70 100
50 200
Выходные данные
112.00000000
Входные данные
2
100 1
100 1
Выходные данные
2.00000000
Входные данные
4
1 100
2 1000
2 100
3 1
Выходные данные
20.00000000
Входные данные
5
34 804
78 209
99 191
61 439
90 79
Выходные данные
395.20423800
Примечание

В первом примере можно выбрать первую и третью игры. В таком случае математическое ожидание выигрыша будет равно $$$\left(\frac{p_1}{100}\cdot \frac{p_3}{100}\right) \cdot (w_1 + w_3) = \left(\frac{80}{100}\cdot \frac{50}{100}\right) \cdot (80 + 200) = 112$$$.

Во втором примере можно выбрать первую и вторую игры. В таком случае математическое ожидание выигрыша будет равно $$$\left(\frac{p_1}{100}\cdot \frac{p_2}{100}\right) \cdot (w_1 + w_2) = \left(\frac{100}{100}\cdot \frac{100}{100}\right) \cdot (1 + 1) = 2$$$.

В третьем примере можно выбрать только вторую игру. В таком случае математическое ожидание выигрыша будет равно $$$\frac{p_2}{100} \cdot w_2 = \frac{2}{100} \cdot 1000 = 20$$$.