Інтеграл усіх жахів#3825

Інтеграл усіх жахів

1 секунда

64 мегабайти

Середня

У відповідь на нафтовий розлив Deep Horizon у $2010$ році, компанія ACME Inc. розробила машину, яка використовує високотехнологічний пучок частинок для дистанційного герметизації нафтових витоків. Для тестування прототипу ACME побудувала підводний випробувальний стенд з $n$ незалежними нафтовими витоками, які називаються $L_{1}, L_{2}, \dots, L_{n}$ L_1, L_2, \ldots, L_n.

Кожен витік $L_{i}$ L_i ( $1 \leq i \leq n$ 1 \le i \le n) характеризується параметрами $r_{i}$ r_i та $t_{i}$ t_i. $r_{i}$ r_i — це початкова швидкість витоку нафти в літрах за секунду (L/s). Поки $L_{i}$ L_i герметизується пучком частинок, швидкість витоку буде лінійно зменшуватися і досягне $0$ L/s (тобто буде герметизовано) через $t_{i}$ t_i секунд безперервної роботи.

Наприклад, нехай $L_{1}$ L_1 характеризується $r_{1} = 20$ r_1 = 20 та $t_{1} = 4$ t_1 = 4. Спочатку нафта витікає зі швидкістю $20$ L/s. Після $1$ секунди герметизації швидкість зменшується до $15$ L/s; після $2$ секунд швидкість становить $10$ L/s; після $3$ s ми маємо $5$ L/s; а після $4$ s витік герметизовано. Протягом цих $4$ секунд загальний об'єм нафти, що витекла з $L_{1}$ L_1, становить $20$ (L/s) $\times$ $4$ (s) $/$ $2 = 40$ 2 = 40 L (площа трикутника). Тим часом з інших витоків продовжує витікати нафта, і вони не зазнають впливу, поки пучок частинок не буде спрямовано на них.

Ви відповідаєте за демонстрацію машини. При $t = 0$ t = 0 ви активуєте пучок для герметизації витоків. Пучок частинок займає незначний час для націлювання на витік і ніколи не простоює. Тому кожен витік герметизується при $t = t_{1} + t_{2} + \dots + t_{n}$ t = t_1 + t_2 + \ldots + t_n (і тоді всі аплодують). Однак під час тесту буде витікати багато нафти. Точна кількість залежить від того, як ви вирішите націлювати пучок частинок протягом демонстрації.

Задані параметри для $L_{1}, L_{2}, \dots, L_{n}$ L_1, L_2, \ldots, L_n, ваше завдання — мінімізувати загальний об'єм (у літрах) витоку нафти між $t = 0$ t = 0 (пучок увімкнено) і $t = t_{1} + t_{2} + \dots + t_{n}$ t = t_1 + t_2 + \ldots + t_n (всі витоки герметизовано). Зверніть увагу, що є декілька тестових випадків (усі незалежні один від одного).

Вхідні дані

Перший рядок вхідних даних містить кількість тестових випадків $N$ , $1 \leq N \leq 50$ 1 \le N \le 50.

Кожен тестовий випадок починається з одного рядка, що містить ціле число $n$ . Кожен з наступних $n$ рядків визначає $L_{i}$ L_i (для $1 \leq i \leq n$ 1 \le i \le n) з двома цілими числами $r_{i}$ r_i та $t_{i}$ t_i, розділеними пробілом.

$n$ — загальна кількість нафтових витоків, і задовольняє $1 \leq n \leq 50$ 1 \le n \le 50.
$r_{i}$ r_i — початкова швидкість витоку (у L/s) для $L_{i}$ L_i, і задовольняє $1 \leq r_{i} \leq 500$ 1 \le r_i \le 500.
$t_{i}$ t_i — загальний час роботи пучка (у s) для герметизації $L_{i}$ L_i, і задовольняє $1 \leq t_{i} \leq 500$ 1 \le t_i \le 500.

Вихідні дані

Для кожного тестового випадку виведіть мінімально можливий загальний об'єм нафти, що витекла під час тесту (у L), з точністю до $2$ десяткових знаків.

Приклади

Приклад 1