Lifeguard Scheduling

Farmer John has hired \(N\) lifeguards to cover his swimming pool from time \(t=0\) to \(t=1,000,000,000\). Each lifeguard \(i\) covers a contiguous interval \([s_i,e_i]\) (with \(e_i - s_i\) units of time, since endpoints are points in time). Unfortunately, he must fire exactly one lifeguard due to budget constraints. Your task is to find the maximum amount of time that remains covered by at least one lifeguard after firing one lifeguard.

An interval is covered if at least one lifeguard is present. The goal is to choose the lifeguard whose removal minimizes the loss in coverage.

Hint: It may be useful to compute the total covered time with all lifeguards and then determine for each lifeguard the amount of time for which they are the only lifeguard on duty (their "unique coverage"). The answer is then the total coverage minus the minimum unique coverage among all lifeguards.

All formulas are rendered in \(\LaTeX\): The pool is open in the interval \([0,1,000,000,000]\) and each lifeguard \(i\) covers the interval \([s_i, e_i]\).

inputFormat

The first line contains an integer \(N\) (the number of lifeguards). Each of the following \(N\) lines contains two integers \(s_i\) and \(e_i\) indicating the start and end times of the \(i\)-th lifeguard's shift.

outputFormat

Output a single integer representing the maximum total time covered by the lifeguards after firing exactly one lifeguard.

sample

3
5 9
1 4
3 7

7