小泽来到一家现购自运商店，将 $n$ 件商品放入了他的手推车，然后到收银台付款。每件商品由它的价格 $c_i$ 和收银员扫描它的时间 $t_i$ 秒定义。

当收银员正在扫描某件商品时，小泽可以从他的手推车中偷走某些其它商品。小泽需要恰好 $1$ 秒来偷走一件商品。小泽需要付给收银员的最少钱数是多少？请记住，收银员扫描商品的顺序由小泽决定。

输入格式

输入第一行包含数 $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$ 时，小泽不能偷任何东西。

输出格式

输出一个数字—— 小泽需要支付的最小金额是多少。

4
2 10
0 20
1 5
1 3

8

3
0 1
0 10
0 100

111

2
880 953844090
1292 978016482

953844090