Internet

Interview

Time limit1sMemory limit1024 MB

Summary

Given measurements with connection states, where the first and last show a connection, find the longest possible time the connection could have been down.

Level: Medium4 of 10
Topics: Greedy, Implementation, Intervals
Solved: No attempts yet

Problem

Tomas's internet connection is often unstable, and sometimes it drops out entirely. Tomas wants to know how long he might have to wait for a dropped connection to come back, so every now and then he checks whether he has an internet connection at that moment and writes it down.

Tomas remembers that he had a connection during both the first and the last measurement.

Help Tomas find the longest time he could possibly have gone without internet.

Input

The first line contains a single integer $N$ , the number of measurements Tomas made.

Each of the next $N$ lines contains two integers $T_i$ and $M_i$ . $T_i$ is the time at which Tomas took the $i$ -th measurement, and $M_i$ is its result: $M_i$ is $1$ if he had an internet connection at that moment, or $0$ if he did not.

The measurements are given in increasing order of $T_i$ .

Output

Print a single integer: the longest time interval during which Tomas could have been without internet.

Constraints

$2 \le N \le 1000$
$1 \le T_i \le 10^6$
$T_i < T_{i+1}$

Examples2

Example 1
Input
```
6
1 1
3 0
4 1
5 0
6 0
8 1
```
Expected output
```
4
```
Example 2
Input
```
4
1 1
2 1
4 1
7 1
```
Expected output
```
3
```