Інтеграл усіх жахів
У відповідь на нафтовий розлив 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_i герметизується пучком частинок, швидкість витоку буде лінійно зменшуватися і досягне 0 Л/с (тобто буде герметизовано) через t_i секунд безперервної роботи.
Наприклад, нехай L_1 характеризується r_1 = 20 та t_1 = 4. Спочатку нафта витікає зі швидкістю 20 Л/с. Після 1 секунди герметизації швидкість зменшується до 15 Л/с; після 2 секунд швидкість становить 10 Л/с; після 3 с ми маємо 5 Л/с; а після 4 с витік герметизовано. Протягом цих 4 секунд загальний об'єм нафти, що витікає з L_1, становить 20 (Л/с) × 4 (с) / 2 = 40 Л (площа трикутника). Тим часом інші витоки продовжують витікати нафту і не зазнають впливу, поки пучок частинок не буде спрямовано на них.
Ви відповідаєте за демонстрацію машини. При 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_i, і задовольняє 1 ≤ r_i ≤ 500.
t_i — загальний час роботи пучка (у с) для герметизації L_i, і задовольняє 1 ≤ t_i ≤ 500.
Вихідні дані
Для кожного тестового випадку виведіть мінімально можливий загальний об'єм нафти, що витекла під час тесту (у Л), з точністю до 2 десяткових знаків.