Farmer John решил собрать панорамную фотографию ряда из $N$ коров ($(1 \le N \le 200,000)$), как всегда пронумерованных $1..N$. Он сделал $M$ снимков ($(1 \le M \le 100,000)$), каждый охватывает непрерывный диапазон: снимок $i$ содержит коров от $a_i$ до $b_i$ включительно. Вместе снимки не обязательно покрывают всех коров.

FJ заметил интересное: на каждом снимке ровно одна пятнистая корова! Он знал, что в стаде есть пятнистые коровы, но не считал их. По снимкам определите максимально возможное число пятнистых коров. Если невозможно назначить пятна в соответствии со всеми снимками, выведите $-1$.

Входные данные

• Строка $1$: целые $N$ и $M$.

• Строки $2..M+1$: строка $i+1$ содержит $a_i$ и $b_i$.

Выходные данные

• Строка $1$: максимально возможное число пятнистых коров, либо $-1$, если решения нет.

Примеры

Входные данные 1

5 3
1 4
2 5
3 4

Выходные данные 1

1

Примечание

Есть $5$ коров и $3$ снимка. Первый содержит коров от $1$ до $4$, и так далее.

Из последнего снимка следует, что пятнистой должна быть либо корова $3$, либо $4$. Выбор любой из них удовлетворяет и первым двум снимкам.

Автор задачи: Brian Dean, 2013