Bob wants to build a house along a river. Unfortunately some parts of the river are occupied by animals and cannot be used. Please write a program to help Bob to calculate the length of the longest continuous river segment that is NOT occupied by any animals.
You can think of the river as a line of length ~L~ from position ~0~ to position ~L~. There are ~N~ animals, each animal occupies a continuous river segment from position ~s~ to ~t~. Note that the segments occupied by animals may be overlapping. Output ~0~ if the whole river is occupied by animals.
- The first line contains an integer ~L~ ~(1 \le L \le 10^9)~ that represents the length of the river.
- The second line contains an integer ~N~ ~(1 \le N \le 100\,000)~ that represents the number of animals.
- Following are ~N~ lines. Each line contains two integers ~s~ and ~t~ ~(0 \le s < t \le L)~ that represent the river segment occupied by one animal.
The length of longest continuous river segment that is not occupied by any animals.
Sample Input 1
5 2 0 2 3 5
Output for Sample Input 1
Sample Input 2
10 2 2 5 4 7
Output for Sample Input 2
Sample Input 3
10 2 0 5 5 10
Output for Sample Input 3
For Sample 1, as 0-2 and 3-5 are occupied, the only remaining part is 2-3.
For Sample 2, the remaining parts are 0-2 and 7-10.