Covering the Day

You are given a day divided into \(M\) time units and \(N\) persons. Each person is willing to work during a time interval \((s_i, e_i)\). If \(s_i \le e_i\) the person can work during \([s_i, e_i]\); if \(s_i > e_i\) it means the person works from \(s_i\) to the end of the day and continues from the beginning of the day until \(e_i\). It is guaranteed that no one’s working period exceeds one full day.

Your task is to choose some persons so that the union of their working intervals covers the entire day (i.e. the interval \([0,M]\)). Output the minimum number of persons needed. If it is impossible to cover the day completely, output -1.

Note: All formulas are rendered in \(\LaTeX\) format.

inputFormat

The first line contains two integers \(M\) and \(N\) (the number of time units in a day and the number of persons, respectively). Each of the next \(N\) lines contains two integers \(s_i\) and \(e_i\) representing a person’s available working time.

Note that if \(s_i \le e_i\), the person works from \(s_i\) to \(e_i\); if \(s_i > e_i\), the person works from \(s_i\) to \(M\) and then from 0 to \(e_i\). You may assume that all intervals are at most one full day in length.

outputFormat

Output a single integer: the minimum number of persons needed to cover the whole day (i.e. the interval \([0,M]\)). If it is impossible to cover the day, output -1.

sample

24 3
0 8
8 16
16 24

3