Lifeguard Scheduling

Farmer John has set up a swimming pool for his cows and hired N lifeguards to ensure safety. The pool is open every day from time \(t=0\) to \(t=1000\). Each lifeguard works a shift described by two integers representing the start and end times. For example, a lifeguard whose shift runs from \(t=4\) to \(t=7\) covers \(7-4=3\) units of time.

Unfortunately, Farmer John has hired one extra lifeguard. He must fire exactly one lifeguard. When at least one lifeguard is on duty a time unit is considered covered. Determine the maximum amount of time that can be covered by the remaining lifeguards after firing exactly one lifeguard.

Note: A lifeguard with a shift from \(s\) to \(e\) covers the time units \(s, s+1, \dots, e-1\). The pool is open from \(t=0\) to \(t=1000\).

inputFormat

The first line contains an integer \(N\) (the number of lifeguards). Each of the next \(N\) lines contains two integers \(s\) and \(e\), representing the start and end times of a lifeguard's shift.

outputFormat

Output a single integer representing the maximum number of time units covered after removing exactly one lifeguard.

sample

3
5 9
1 4
3 7

7