Дежурные на переменах

В школе идёт длинная перемена длительностью L минут — от момента 0 до момента L. Учителя-добровольцы готовы дежурить только в своих промежутках времени.

Завучу хочется, чтобы в каждую минуту перемены в коридоре дежурил хотя бы один учитель. Помогите понять, какое минимальное число учителей нужно выбрать. Если это невозможно, выведите -1.

Формат ввода

В первой строке записаны два целых числа L и n — длительность перемены и число учителей. Далее идут n строк, в каждой два целых числа aᵢ и bᵢ — время начала и конца дежурства i-го учителя.

Формат вывода

Выведите одно целое число — минимальное количество выбранных учителей, чтобы все моменты времени от 0 до L были покрыты дежурством, или -1, если это невозможно.

Ограничения

• 1 ≤ L ≤ 10^9
• 1 ≤ n ≤ 2·10^5
• 0 ≤ aᵢ < bᵢ ≤ L

Пример

Ввод:

10 4
0 3
2 7
6 10
3 6

Вывод:

3