Вася пришел в магазин cash-n-carry, положил в корзину n товаров и пошел на кассу оплачивать покупку. Каждый товар характеризуется ценой ci и временем ti в секундах, в течение которого кассир пробивает этот товар. За время, пока кассир пробивает товар, Вася может украсть некоторые другие свои покупки из корзины. На то, чтобы своровать один товар, Вася тратит ровно 1 секунду. Какое наименьшее количество денег Васе придется заплатить? Помните, что порядок, в котором кассир будет пробивать товар, определяет Вася.
Выходные данные
Выведите одно число — ответ на задачу: какое наименьшее количество денег придется заплатить Васе.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
2 10
0 20
1 5
1 3
|
8
|
|
2
|
3
0 1
0 10
0 100
|
111
|