C. Выносливость и задачи
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть $$$n$$$ задач. Задача $$$i$$$ имеет целочисленную ценность $$$c_i$$$ и сложность $$$p_i$$$. Также у вас есть начальная выносливость, равная $$$1$$$, обозначаемая как $$$S$$$. Вам нужно обрабатывать задачи с задачи $$$1$$$ до задачи $$$n$$$. Для каждой задачи у вас есть два выбора.

  • Сдаться по задаче. В этом случае ничего не произойдет.
  • Выполнить задачу. В этом случае вы получите $$$S\cdot c_i$$$ очков. Однако $$$S$$$ упадет до $$$S\cdot (1-\frac{p_i}{100})$$$ после выполнения задачи.

Вам нужно максимизировать свои очки после завершения процесса.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^3$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$1\le n\le10^5$$$), обозначающее количество задач.

Следующие $$$n$$$ строк содержат по два целых числа, обозначающих $$$c_i$$$ ($$$1\le c_i\le 100$$$) и $$$p_i$$$ ($$$0\le p_i\le 100$$$).

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

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

Для каждого набора входных данных выведите одно вещественное число — максимальное количество очков, которое вы можете получить. Ваш ответ считается правильным, если его абсолютная или относительная погрешность не превосходит $$$10^{-6}$$$.

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

Пример
Входные данные
2
2
10 0
20 5
3
10 5
10 80
20 5
Выходные данные
30.0000000000
29.0000000000
Примечание

В первом наборе входных данных оптимально выполнить задачи $$$1$$$ и $$$2$$$ по порядку, получив $$$10+20=30$$$ очков.

Во втором наборе входных данных оптимально выполнить задачу $$$1$$$, сдаться по задаче $$$2$$$ и выполнить задачу $$$3$$$. Перед выполнением задачи $$$3$$$ ваша выносливость упала до $$$1-\frac{5}{100}=0.95$$$. Таким образом, ваш выигрыш составляет $$$10+20\cdot 0.95=29$$$ очков в сумме.