Escalator

Interview

Time limit1sMemory limit1024 MB

Summary

Simulate a bidirectional escalator that carries riders in 10-second trips, where riders going against the current direction wait, and report the time the last rider exits.

Level: Medium4 of 10
Topics: Simulation, Implementation, Queue, Sorting
Solved: No attempts yet

Problem

You have just invented a new type of escalator: the double escalator. Regular escalators take people from one endpoint to another but not in the other direction, while the double escalator can take people from any one of its endpoints to the other one.

It takes 10 seconds for the double escalator to take a person from any of its endpoints to the other one. That is, if a person enters the double escalator from one of the endpoints at moment T, then they will leave at the other endpoint at moment T + 10. This person won't be using the double escalator anymore at moment T + 10.

Any time that no one is using the double escalator, it will stop immediately. Thus, it is initially stopped.

When the double escalator is stopped and a person enters it from one of its endpoints, it will turn on automatically and move in the direction that this person wants to go.

If a person arrives at the double escalator and it is already moving in the direction that they want to go, they will enter it immediately. Otherwise, if it's moving in the opposite direction that they want to go, they will wait until it stops, and only then will they enter it. The escalator is so large that it can accommodate many people entering it at the same time.

The double escalator has a very weird effect, probably related to some quantum physics effect (or just chance): no person will ever arrive on the double escalator at the exact moment the escalator stops.

Now that you know how the double escalator works, you will be given the task of simulating it. Given the information about N people, including their time of arrival at the escalator and which direction they want to go, you have to figure out the last moment that the escalator stops.

Input

The first line contains one integer N (1 ≤ N ≤ 10^4), representing the number of people that will use the double escalator.

Each of the next N lines contains two integers t_i and d_i (1 ≤ t_i ≤ 10^5, 0 ≤ d_i ≤ 1), representing the time that the i-th person will arrive at the escalator and which direction they want to go. If d_i is equal to 0, they want to go from the left to the right endpoint, and if d_i is equal to 1, they want to go from the right to the left endpoint. All values of t_i are distinct and will be given in ascending order.

Output

Output one line containing the time that the last person will leave the double escalator.

Examples3

Example 1
Input
```
3
5 0
8 0
13 0
```
Expected output
```
23
```
Example 2
Input
```
3
5 0
7 1
9 0
```
Expected output
```
29
```
Example 3
Input
```
3
5 0
10 1
16 0
```
Expected output
```
35
```