Интеграл всех ужасов
В ответ на разлив нефти Deep Horizon в 2010 году компания ACME Inc. разработала устройство, которое использует высокотехнологичный пучок частиц для дистанционного запечатывания утечек нефти. Для тестирования прототипа ACME создала подводный испытательный стенд с n независимыми утечками нефти, обозначенными как L_1, L_2, ..., L_n.
Каждая утечка L_i (1 ≤ i ≤ n) характеризуется параметрами r_i и t_i. r_i — это начальная скорость утечки нефти в литрах в секунду (L/s). Пока L_i запечатывается пучком частиц, скорость утечки будет линейно уменьшаться и достигнет 0 L/s (т.е. будет запечатана) через t_i секунд непрерывной работы.
Например, если L_1 характеризуется r_1 = 20 и t_1 = 4, то изначально нефть вытекает со скоростью 20 L/s. Через 1 секунду запечатывания скорость уменьшается до 15 L/s; через 2 секунды скорость составляет 10 L/s; через 3 секунды она равна 5 L/s; и через 4 секунды утечка запечатана. За эти 4 секунды общий объем нефти, вытекшей из L_1, составляет 20 (L/s) × 4 (s) / 2 = 40 L (площадь треугольника). Между тем, другие утечки продолжают вытекать нефть и не затрагиваются, пока пучок частиц не будет направлен на них.
Вы отвечаете за демонстрацию машины. В момент t = 0 вы активируете пучок для запечатывания утечек. Пучок частиц занимает незначительное время для наведения на утечку и никогда не простаивает. Таким образом, каждая утечка будет запечатана в момент t = t_1 + t_2 + ... + t_n (и тогда все аплодируют). Однако во время теста будет вытекать много нефти. Точное количество зависит от того, как вы решите направлять пучок частиц в течение демонстрации.
Даны параметры для L_1, L_2, ..., L_n, ваша задача — минимизировать общий объем (в литрах) утечки нефти между t = 0 (пучок включен) и t = t_1 + t_2 + ... + t_n (все утечки запечатаны). Обратите внимание, что имеется несколько тестовых случаев (все независимы друг от друга).
Входные данные
Первая строка ввода содержит количество тестовых случаев N, 1 ≤ N ≤ 50.
Каждый тестовый случай начинается с одной строки, содержащей целое число n. Каждая из следующих n строк задает L_i (для 1 ≤ i ≤ n) двумя целыми числами r_i и t_i, разделенными пробелом.
n — общее количество утечек нефти и удовлетворяет условию 1 ≤ n ≤ 50.
r_i — начальная скорость утечки (в L/s) для L_i и удовлетворяет условию 1 ≤ r_i ≤ 500.
t_i — общее время работы пучка (в s) для запечатывания L_i и удовлетворяет условию 1 ≤ t_i ≤ 500.
Выходные данные
Для каждого тестового случая выведите минимально возможный общий объем вытекшей нефти во время теста (в L), с точностью до 2 десятичных знаков.