Жемчуг
В Перлании все обожают жемчуг. Компания под названием 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). Качество классов (и, следовательно, цены) даны в порядке возрастания. Все числа во входных данных — целые.
Выходные данные
Для каждого теста выведите одну строку, содержащую одно число: наименьшая возможная цена, необходимая для покупки всего в списке.