CF1503C.Travelling Salesman Problem

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

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.

输入格式

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.

输出格式

Output a single integer — the minimum total cost.

输入输出样例

输入#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
```

说明/提示

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.

首页