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