Match Scheduling Optimization

In a tournament, each match has a range of days during which it can be played. The i-th match can be scheduled on any day in the interval ( [a_i, b_i] ). However, no two matches can be held on the same day. Your task is to assign a day to each match such that every match is scheduled within its available interval and the maximum day used (which represents the span of days required) is minimized.

For example, if there are 3 matches with intervals ((1,2)), ((2,3)), and ((3,4)), an optimal scheduling is to play them on days 1, 2, and 3 respectively, so the tournament spans 3 days.

inputFormat

The first line of input contains two integers ( n ) and ( m ) where ( n ) is the total number of days available in the tournament (though not necessarily all used) and ( m ) is the number of matches. Each of the following ( m ) lines contains two integers ( a_i ) and ( b_i ) ((1 \leq a_i \leq b_i \leq n)), representing the range of days during which the i-th match can be scheduled.

outputFormat

Output a single integer representing the minimum possible maximum day used to schedule all matches, following the constraint that each match must be played on a distinct day within its available interval.## sample

4 3
1 2
2 3
3 4

3