Codeforces Round 313 (Div. 1) |
---|

Finished |

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.

dp

sortings

*3000

No tag edit access

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

×
E. Gerald and Path

time limit per test

4 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThe main walking trail in Geraldion is absolutely straight, and it passes strictly from the north to the south, it is so long that no one has ever reached its ends in either of the two directions. The Geraldionians love to walk on this path at any time, so the mayor of the city asked the Herald to illuminate this path with a few spotlights. The spotlights have already been delivered to certain places and Gerald will not be able to move them. Each spotlight illuminates a specific segment of the path of the given length, one end of the segment is the location of the spotlight, and it can be directed so that it covers the segment to the south or to the north of spotlight.

The trail contains a monument to the mayor of the island, and although you can walk in either directions from the monument, no spotlight is south of the monument.

You are given the positions of the spotlights and their power. Help Gerald direct all the spotlights so that the total length of the illuminated part of the path is as much as possible.

Input

The first line contains integer *n* (1 ≤ *n* ≤ 100) — the number of spotlights. Each of the *n* lines contains two space-separated integers, *a*_{i} and *l*_{i} (0 ≤ *a*_{i} ≤ 10^{8}, 1 ≤ *l*_{i} ≤ 10^{8}). Number *a*_{i} shows how much further the *i*-th spotlight to the north, and number *l*_{i} shows the length of the segment it illuminates.

It is guaranteed that all the *a*_{i}'s are distinct.

Output

Print a single integer — the maximum total length of the illuminated part of the path.

Examples

Input

3

1 1

2 2

3 3

Output

5

Input

4

1 2

3 3

4 3

6 2

Output

9

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/31/2023 23:34:08 (l1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|