CF1503C.Travelling Salesman Problem

There are $n$ cities numbered from $1$ to $n$, and city $i$ has beauty $a_i$.

A salesman wants to start at city $1$, visit every city exactly once, and return to city $1$.

For all $i\ne j$, a flight from city $i$ to city $j$ costs $\max(c_i,a_j-a_i)$ dollars, where $c_i$ is the price floor enforced by city $i$. Note that there is no absolute value. Find the minimum total cost for the salesman to complete his trip.

有 $n$ 座城市，编号从 $1$ 到 $n$，其中城市 $i$ 的美丽值为 $a_i$。

一名推销员希望从城市 $1$ 出发，恰好访问每座城市一次，并最终返回城市 $1$。

对于所有 $i \ne j$，从城市 $i$ 飞往城市 $j$ 的航班费用为 $\max(c_i, a_j - a_i)$ 美元，其中 $c_i$ 是城市 $i$ 规定的价格下限。注意：此处没有绝对值。求推销员完成该环游的最小总费用。

The first line contains a single integer $n$ ($2\le n\le 10^5$) — the number of cities.

The $i$-th of the next $n$ lines contains two integers $a_i$, $c_i$ ($0\le a_i,c_i\le 10^9$) — the beauty and price floor of the $i$-th city.

第一行包含一个整数 $n$（$2\le n\le 10^5$）—— 城市的数量。

接下来的 $n$ 行中，第 $i$ 行包含两个整数 $a_i$、$c_i$（$0\le a_i,c_i\le 10^9$）—— 第 $i$ 个城市的美丽值和价格下限。

Output a single integer — the minimum total cost.

输出一个整数——最小总成本。

In the first test case, we can travel in order $1\to 3\to 2\to 1$.

• The flight $1\to 3$ costs $\max(c_1,a_3-a_1)=\max(9,4-1)=9$.
• The flight $3\to 2$ costs $\max(c_3, a_2-a_3)=\max(1,2-4)=1$.
• The flight $2\to 1$ costs $\max(c_2,a_1-a_2)=\max(1,1-2)=1$.

The total cost is $11$, and we cannot do better.

在第一个测试用例中，我们可以按顺序 $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$，且无法得到更优解。