Checkout Assistant

### 题目描述 Bob 来到一家现购自运商店，将 $n$ 件商品放入了他的手推车，然后到收银台付款。每件商品由它的价格 $c_i$ 和收银员扫描它的时间 $t_i$ 秒定义。 当收银员正在扫描某件商品时，Bob 可以从他的手推车中偷走某些其它商品。Bob 需要恰好 $1$ 秒来偷走一件商品。Bob 需要付给收银员的最少钱数是多少？请记住，收银员扫描商品的顺序由 Bob 决定。 ### 输入格式 输入第一行包含数 $n$（$1 \le n \le 2000$）。接下来 $n$ 行每行每件商品由一对数 $t_i$，$c_i$（$0 \le t_i \le 2000$，$1 \le c_i \le 10^9$）描述。如果 $t_i$ 是 $0$，那么当收银员扫描商品 $i$ 时，Bob 不能偷任何东西。 ### 输出格式 输出一个数字—— Bob 需要支付的最小金额是多少。

Bob came to a cash & carry store, put $ n $ items into his trolley, and went to the checkout counter to pay. Each item is described by its price $ c_{i} $ and time $ t_{i} $ in seconds that a checkout assistant spends on this item. While the checkout assistant is occupied with some item, Bob can steal some other items from his trolley. To steal one item Bob needs exactly 1 second. What is the minimum amount of money that Bob will have to pay to the checkout assistant? Remember, please, that it is Bob, who determines the order of items for the checkout assistant.

The first input line contains number $ n $ ( $ 1<=n<=2000 $ ). In each of the following $ n $ lines each item is described by a pair of numbers $ t_{i} $ , $ c_{i} $ ( $ 0<=t_{i}<=2000,1<=c_{i}<=10^{9} $ ). If $ t_{i} $ is 0, Bob won't be able to steal anything, while the checkout assistant is occupied with item $ i $ .

Output one number — answer to the problem: what is the minimum amount of money that Bob will have to pay.

4
2 10
0 20
1 5
1 3

8

3
0 1
0 10
0 100

111