CF1503C Travelling Salesman Problem

有 $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\to 3\to 2\to 1$ 旅行。 - 航班 $1\to 3$ 的费用为 $\max(c_1, a_3-a_1)=\max(9,4-1)=9$。 - 航班 $3\to 2$ 的费用为 $\max(c_3, a_2-a_3)=\max(1,2-4)=1$。 - 航班 $2\to 1$ 的费用为 $\max(c_2, a_1-a_2)=\max(1,1-2)=1$。 总费用为 $11$，无法更优。 由 ChatGPT 4.1 翻译