Duff не может прожить без мяса! Malek покупает ей мясо в течение n дней. Организм девушки в i-й день требует ровно ai килограммов мяса.
Неподалеку есть большой магазин, в котором Malek хочет закупаться мясом для девушки там. На i-й день там продают мясо по pi долларов за килограмм. Malek знает все числа a1, ..., an и p1, ..., pn. Каждый день он может покупать произвольное количество мяса, также он может отложить часть купленного мяса на потом.
Malek постоянно занять готовкой мяса, так что он пропросил Вас о помощи. Помогите ему минимизировать общую сумму денег, потраченных им на то, чтобы радовать Duff на протяжении n дней.
В первой строке записано целое число n (1 ≤ n ≤ 105), количество дней.
Далее следуют n строк, i-я из них содержит два целых числа, ai и pi (1 ≤ ai, pi ≤ 100), количество мяса, необходимого Duff и цена на мясо в этот день.
Выведите минимульную сумму, необходимую для того, чтобы радовать Duff n дней.
3
1 3
2 2
3 1
10
3
1 3
2 1
3 2
8
В первом тесте оптимальная стратегия будет: купить 1 кг в первый день, 2 кг во второй день и 3 кг в третий день.
Во втором тесте оптимальная стратегия будет: купить 1 кг в первый день и 5 кг (мясо на второй и третий дни) во второй день.
