Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
C. Travelling Salesman Problem

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThere 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.

Input

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

Output a single integer — the minimum total cost.

Examples

Input

3 1 9 2 1 4 1

Output

11

Input

6 4 2 8 4 3 0 2 3 7 1 0 1

Output

13

Note

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.

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/16/2021 20:26:17 (i1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|