B. Кассир
ограничение по времени на тест
1 second
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Вася пришел в магазин cash-n-carry, положил в корзину n товаров и пошел на кассу оплачивать покупку. Каждый товар характеризуется ценой ci и временем ti в секундах, в течение которого кассир пробивает этот товар. За время, пока кассир пробивает товар, Вася может украсть некоторые другие свои покупки из корзины. На то, чтобы своровать один товар, Вася тратит ровно 1 секунду. Какое наименьшее количество денег Васе придется заплатить? Помните, что порядок, в котором кассир будет пробивать товар, определяет Вася.

Входные данные

В первой строке задано число n (1 ≤ n ≤ 2000). В каждой из n следующих строк задано описание одного товара парой чисел ti, ci (0 ≤ ti ≤ 2000, 1 ≤ ci ≤ 109). Если ti равно 0, то у Васи не получится украсть ни одного товара за время, пока кассир обрабатывает товар номер i.

Выходные данные

Выведите одно число — ответ на задачу: какое наименьшее количество денег придется заплатить Васе.

Примеры
Входные данные
4
2 10
0 20
1 5
1 3
Выходные данные
8
Входные данные
3
0 1
0 10
0 100
Выходные данные
111