← 返回题目列表

Codeforces · 1503/C

C. 旅行商问题

中文机器翻译题面 查看原题

有$$$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$$$,我们不能做得更好了。