有$$$n$$$个城市,编号从$$$1$$$到$$$n$$$,城市$$$i$$$有美丽的$$$a_i$$$。
一名推销员希望从城市 $$$1$$$ 开始,访问每个城市一次,然后返回城市 $$$1$$$。
对于所有 $$$i\ne j$$$,从城市 $$$i$$$ 飞往城市 $$$j$$$ 的费用为 $$$\max(c_i,a_j-a_i)$$$ 美元,其中 $$$c_i$$$ 是城市 $$$i$$$ 强制执行的价格下限。请注意,没有绝对值。求推销员完成行程的最低总成本。
输入
第一行包含一个整数 $$$n$$$ ($$$2\le n\le 10^5$$$) — 城市数量。
接下来的 $$$n$$$ 行的第 $$$i$$$ 行包含两个整数 $$$a_i$$$、$$$c_i$$$ ($$$0\le a_i,c_i\le 10^9$$$) — 第 $$$i$$$ 城市的美丽和价格下限。
输出
输出一个整数——最小总成本。
示例
输入 #1
3 1 9 2 1 4 1
输出 #1
11
输入 #2
6 4 2 8 4 3 0 2 3 7 1 0 1
输出 #2
13
注意
在第一个测试用例中,我们可以按 $$$1\to 3\to 2\to 1$$$ 的顺序行驶。
- $$$1\飞往 3$$$ 的航班费用为 $$$\max(c_1,a_3-a_1)=\max(9,4-1)=9$$$。
- $$$3\飞往 2$$$ 的航班费用为 $$$\max(c_3, a_2-a_3)=\max(1,2-4)=1$$$。
- $$$2\飞往 1$$$ 的航班费用为 $$$\max(c_2,a_1-a_2)=\max(1,1-2)=1$$$。
总成本为 $$$11$$$,我们不能做得更好了。