说明

时间限制：1 Sec 内存限制：256 MB 输入文件：shopping.in 输出文件：shopping.out

小明计划在商店购买 $N$ 件商品。第 $i$ 件商品有售价 $C_i$ 和包装费 $D_i$。购买顺序固定，必须按照编号从小到大依次购买。

在商店购物存在以下收费规则：

1. 每购买一件商品，都要支付该商品本身的售价。

2. 同一天内购买的第 $2$ 件及之后的所有商品，额外加收这件商品的包装费。

3. 只要当天至少购买一件商品，就会收取一笔手续费，手续费金额等于当天所购商品中最便宜那件的售价。

小明发现，把商品分多天购买有可能降低总花费。请你求出小明采用最优购买方案时，需要支付的最小总费用。

输入格式

第一行一个整数 $N$，代表商品总数。

接下来 $N$ 行，每行两个整数 $C_i,D_i$，$C_i$ 为第 $i$ 件商品的售价，$D_i$ 为第 $i$ 件商品的包装费。

输出格式

输出一行一个整数，表示最小总花费。

样例

样例 1

3
20 5
10 3
30 12

85

样例说明：

最优方案是一天买完三件商品：

0 号商品：售价 $20$；

1 号商品：售价 $10$，加收包装费 $3$；

2 号商品：售价 $30$，加收包装费 $12$；

当日手续费为当天最便宜商品（1 号）的价格 $10$。

总花费：$20+(10+3)+(30+12)+10=85$。

样例 2

2
10 30
15 20

50

样例说明：

最优方案是分两天各买一件：

第一天买 0 号：售价 $10$，手续费 $10$；

第二天买 1 号：售价 $15$，手续费 $15$；

总花费：$10+10+15+15=50$。

补充说明：如果一天买两件总花费为 $55$，不如分开划算。

样例 3

10
120 63
65 31
58 80
61 59
80 75
110 63
58 12
91 80
30 30
71 53

1203

数据范围

对于 10% 的数据，$N \le 30$，$C_i,D_i \le 100$。

对于 15% 的数据，$N \le 100$。$C_i,D_i \le 1000$。

对于 20% 的数据，$N \le 1000$。$C_i,D_i \le 10^5$。

对于 100% 的数据，满足 $1 \le N \le 10^5$，$1 \le C_i \le 10^9$，$1 \le D_i \le 10^9$。