An engineer needs to schedule a machine to run on some given periods 1;..., n to produce a chemical product C. Each period i is represented by a starting time point s$i$ and terminating time point t$i$ (s$i$ < t$i$). Due to a technical constraint, the machine must run on exactly two periods that are not overlap (two periods i and j are not overlap if t$i$ < s$j$ or t$j$ < s$i$). If the machine is runned on the period i, then the amount of C it will produce is equal to the duration of the period i (which is equal to t$i$-s$i$). Help the engineer to select two not-overlap periods to run the machine such that the amount of C produced is maximal.

Input

The input consists the following lines:

? Line 1: contains the positive integer n (2 = < n = < 10^6)

? Line i + 1: contains two positive integer s$i$ and t$i$ (1 = < s$i$ < t$i$ = < 10^6)

Output

The output consists of only one single integer which is the amount of product C the machine will produce in the two selected periods. In case there is no solution (there does not exist two periods that are not overlap), the output contains the value -1.

Example

Input

5

8 12

6 11

3 9

2 5

1 4

Input

8

Explanation

The machine will be runned on two periods [2, 5] and [6, 11] and produce 8 unit of product C.