Back in the day, lamplighters turned on your street lights! In this peculiar city, there are ~N~ street lights numbered ~1~ to ~N~. Every minute, one lamplighter would walk from ~L_i~-th to ~R_i~-th street lamp (inclusive), turning them all on. How many full minutes will it take for all of the street lights to turn on?

Constraints

~1\le N\le 1000~

~1\le M\le 2000~

~1\le L_i\le R_i\le N~

Input Specification

The first line contains ~N~ and ~M~, the number of street lamps and the number of minutes to consider.

The next ~M~ lines contains ~L_i~ and ~R_i~, the ~j~-th line describing the lamplighter moving at the ~j~-th minute.

Output Specification

One integer, the number of full minutes before all of the street lights are turned on. It is guaranteed that all of the street lights will be turned on by the ~M~ minute.

Sample Input

6 4
1 4
3 5
2 6
3 4

Sample Output

3

Sample Explanation

In the first two minutes, the sixth lamp isn't turned on. However, once the third minute completes, the ranges 1 4, 3 5 and 2 6 are covered, which covers all of the lamps from 1 to 6. So, it'll take 3 minutes.