Недавно вы получили редчайший билет в единственное казино в мире, в котором и правда можно что-то заработать, и вы хотите на полную воспользоваться этой возможностью.
Условия в этом казино следующие:
- Всего в казино есть \(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\).
Ваша задача — найти максимальное математическое ожидание выигрыша, которое можно получить, выбрав какой-то набор игр в казино.
Выходные данные
Выведите одно число — максимальное математическое ожидание выигрыша в казино, которое можно получить, выбрав некоторое подмножество игр.
Ваш ответ будет засчитан, если относительная или абсолютная погрешность не будет превышать \(10^{-6}\). Формально, если \(a\) — ваш ответ, а \(b\) — ответ жюри, то он будет засчитан, если \(\frac{|a-b|}{\max(b, 1)} \le 10^{-6}\).
Примечание
В первом примере можно выбрать первую и третью игры. В таком случае математическое ожидание выигрыша будет равно \(\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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
80 80
70 100
50 200
|
112.00000000
|
|
2
|
2
100 1
100 1
|
2.00000000
|
|
3
|
4
1 100
2 1000
2 100
3 1
|
20.00000000
|
|
4
|
5
34 804
78 209
99 191
61 439
90 79
|
395.20423800
|