The Lion Is the King of Travel!!

Ryan really loves to travel. He used to say that a day without traveling would grow thorns in his mouth, but after traveling that much his stamina and budget could not keep up, so he decided to change his goal to making the periods when he is not traveling as short as possible.

Ryan plans his trips as follows. First, he makes a list of where he can go and for which periods. These periods come from considering many factors such as transportation, holidays, and events that are held only on particular days, so they cannot be changed. In other words, for each destination on the list he can only choose either to go for exactly the given period or not to go. Since he cannot travel to two places at the same time, the periods of the chosen destinations must not overlap. One could imagine a schedule where he returns from destination A in the morning and leaves for destination B in the afternoon, but for the sake of his stamina he decided not to make such schedules.

As stated above, Ryan's goal is to make the periods when he is not traveling as short as possible. That is, he wants a plan that minimizes the maximum length of the periods when he is not traveling. For example, suppose he plans a trip over the period from July 1 to July 31. The list of destinations and their periods is as follows.

• Jeju: July 20 to July 23
• London: July 3 to July 14
• Tokyo: July 5 to July 7
• Hong Kong: July 12 to July 15
• Hawaii: July 24 to July 29

Examples of ways to choose non-overlapping destinations are London, Jeju, Hawaii, and Tokyo, Hong Kong, Jeju, Hawaii. For the former, the periods when he is not traveling are July 1 to 2, July 15 to 19, and July 30 to 31, and the longest of these is 5 days. For the latter, the periods when he is not traveling are July 1 to 4, July 8 to 11, July 16 to 19, and July 30 to 31, and the longest of these is 4 days. By Ryan's standard the maximum length of the periods when he is not traveling must be minimized, so he must choose the destinations of the latter.

Given the interval over which he plans the trip and the candidate travel periods, find a way to minimize the maximum length of the periods when he is not traveling (the length of the longest period among the periods when he is not traveling) and output that length.

The first line contains N (1 ≤ N ≤ 1,000), the length of the interval over which he plans the trip.

The second line contains M (1 ≤ M ≤ 1,000), the number of candidate travel periods.

The next M lines each contain two integers ai and bi (1 ≤ ai ≤ bi ≤ N), the start and end of a travel period. Each value is the number of the day counted from the start day, and the first day of the interval corresponds to 1.

On the first line, output the minimum possible maximum length of the periods when he is not traveling.