超市购物

题目描述

Y 同学来到了一家现购自运的商店，他的手推车里装满了 $N$ 件商品。他来到收银台准备结账。

每件商品 $i$ 都有两个属性：价格 $c_i$ 和收银员扫描该商品所需的时间 $t_i$ 秒。

结账的规则如下：

1. 收银员扫描商品是由 Y 同学决定的顺序进行的。
2. 当收银员正在扫描某件商品 $i$ 时（耗时 $t_i$ 秒），Y 同学利用这段时间，可以从手推车中把其他任意 $t_i$ 件商品“免费”带走（每秒带走 $1$ 件，不经过扫描，也就无需支付费用）。
3. 当然，Y 同学也可以选择支付某件商品的费用 $c_i$，让收银员扫描它，从而获得处理其他商品的时间。

为了合法地带走所有 $N$ 件商品，每件商品必须要么是被收银员扫描并付款的，要么是在扫描其他商品期间被“免费”带走的。

请你帮助 Y 同学计算，为了带走所有 $N$ 件商品，他需要支付给收银员的最小总金额是多少。

输入格式

第一行包含一个整数 $N$，表示商品的数量。

接下来 $N$ 行，每行包含两个整数 $t_i$ 和 $c_i$，分别表示第 $i$ 件商品的扫描时间（秒）和价格。

输出格式

输出一行一个整数，表示 Y 同学需要支付的最小金额。

样例

样例输入 #1

4
2 10
0 20
1 5
1 3

样例输出 #1

8

样例输入 #2

3
0 1
0 10
0 100

样例输出 #2

111

数据范围与约定

对于 $100\%$ 的数据，保证 $1 \le N \le 2000$， $0 \le t_i \le 2000$， $1 \le c_i \le 10^9$。