Перлини
У Перланії всі захоплюються перлами. Компанія під назвою The Royal Pearl виробляє безліч прикрас з перлами. Вона отримала таку назву, тому що постачає прикраси королівській родині Перланії. Проте, компанія також виготовляє браслети та намиста для звичайних людей. Звісно, якість перлів для цих людей значно нижча, ніж для королівської родини. У Перланії перли поділяються на 100 різних класів якості. Клас якості визначається ціною за один перл у цьому класі, і ця ціна є унікальною та завжди вищою, ніж у нижчому класі.
Щомісяця менеджер зі складу The Royal Pearl складає список з кількістю перлів, необхідних у кожному класі якості. Перли купуються на місцевому ринку, і кожен клас має свою ціну за перл. Однак, за кожну повну угоду в певному класі якості потрібно заплатити додаткову суму, що дорівнює ціні десяти перлів у цьому класі. Це робиться, щоб запобігти купівлі туристами лише одного перла.
The Royal Pearl також відчуває вплив уповільнення світової економіки, тому компанія прагне підвищити ефективність. Фінансовий директор (CFO) виявив, що іноді можна заощадити, купуючи перли вищого класу якості, ніж це фактично потрібно. Жоден клієнт не буде скаржитися на використання кращих перлів у браслетах, якщо ціни залишаються незмінними.
Наприклад, якщо потрібно 5 перлів у категорії 10 євро та 100 перлів у категорії 20 євро, це зазвичай коштує: (5+10)*10+(100+10)*20 = 2350 євро. Купівля всіх 105 перлів у категорії 20 євро коштує лише: (5+100+10)*20 = 2300 євро.
Проблема в тому, що потрібно багато обчислень, щоб фінансовий директор дізнався, скільки перлів краще купити у вищому класі якості. Вас просять допомогти The Royal Pearl з комп'ютерною програмою.
Дано список з кількістю перлів і ціною за перл у різних класах якості, визначте найнижчу можливу ціну, необхідну для купівлі всього зі списку. Перли можна купувати у запитуваному або у вищому класі якості, але не у нижчому.
Вхідні дані
Перша строка вхідних даних містить кількість тестових випадків. Кожен тестовий випадок починається з рядка, що містить кількість категорій c (1 ≤ c ≤ 100). Далі йдуть c рядків, кожен з яких містить два числа a_i та p_i. Перше з цих чисел - це кількість перлів a_i, необхідних у класі (1 ≤ a_i ≤ 1000).
Друге число - це ціна за перл p_i у цьому класі (1 ≤ p_i ≤ 1000). Якість класів (і, відповідно, ціни) подані у зростаючому порядку. Усі числа у вхідних даних є цілими.
Вихідні дані
Для кожного тестового випадку виведіть один рядок, що містить одне число: найнижчу можливу ціну, необхідну для купівлі всього зі списку.