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 from position to position . There are animals, each animal occupies a continuous river segment from position to . Note that the segments occupied by animals may be overlapping. Output if the whole river is occupied by animals.
- The first line contains an integer that represents the length of the river.
- The second line contains an integer that represents the number of animals.
- Following are lines. Each line contains two integers and 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.