Lifeguards

Time limit2sMemory limit512 MB

Summary

Given N shifts, remove exactly one so that the total time covered by the remaining shifts is maximized.

Level: Easy3 of 10
Topics: Intervals, Brute force, Array
Solved: No attempts yet

Problem

Farmer John has opened a swimming pool for his cows, expecting that it helps them relax and produce more milk.

For safety he hires $N$ cows as lifeguards, and each of them works a shift that covers one contiguous interval of the day. The pool is open every day from time $t=0$ until time $t=1000$ , so a shift is described by two integers: the time a cow starts her shift and the time she ends it. A lifeguard who starts at time $t=4$ and ends at time $t=7$ covers three units of time. Times are points, and the length of a shift is the end time minus the start time.

Farmer John hired one more lifeguard than his budget supports. Given that he must fire exactly one of them, what is the maximum amount of time that the shifts of the remaining lifeguards still cover? A unit of time is covered when at least one lifeguard is on duty during it.

Input

The first line contains $N$ ( $1 \leq N \leq 100$ ). Each of the next $N$ lines describes one lifeguard with two integers, the starting point and the ending point of her shift. Both values are between $0$ and $1000$ , and the starting point is smaller than the ending point. The $2N$ endpoints in the input are all distinct. Shifts of different lifeguards might overlap.

Output

Print a single integer, the maximum amount of time that can still be covered after Farmer John fires one lifeguard.

Examples3

Example 1
Input
```
3
5 9
1 4
3 7
```
Expected output
```
7
```
Example 2
Input
```
2
0 1000
400 600
```
Expected output
```
1000
```
Example 3
Input
```
3
10 40
41 70
71 99
```
Expected output
```
59
```