Minimum Cow Duty Assignment

John has a day divided into \(T\) time slots (\(1 \le T \le 10^6\)). He plans to assign his \(N\) cows (\(1 \le N \le 2.5\times10^4\)) for duty to clean the barn. Each cow is available only during her free time interval \([S_i, E_i]\) (where \(1 \le S_i \le E_i \le T\)). A cow can be assigned for duty only if it is within her available interval. In addition, every time slot from 1 to \(T\) must have at least one cow on duty.

Your task is to determine the minimum number of cows required to cover all \(T\) time slots. If it is impossible to cover the whole day, output \(-1\).

inputFormat

The first line contains two integers \(T\) and \(N\) separated by a space.

Each of the following \(N\) lines contains two integers \(S_i\) and \(E_i\), describing the free time interval of a cow.

\(1 \le T \le 10^6, \; 1 \le N \le 2.5\times10^4, \; 1 \le S_i \le E_i \le T\).

outputFormat

Output a single integer representing the minimum number of cows required. If it is not possible to cover every time slot, output \(-1\).

sample

10 3
1 5
4 10
6 8

2