Имеется числовая прямая длиной $N-1$. Ваша цель — добраться от $1$ до $N$ за минимальное время. В течение $T$ минут каждую минуту происходит контроль.

Контроль в $t$-ю минуту задается двумя целыми числами $l_t$ и $r_t$. Если в момент времени $t+0.5$ ваша позиция $x$ удовлетворяет условию $(l_t \le x \le r_t)$, вы немедленно проигрываете. Если $t > T$, контроль не осуществляется.

Каждую минуту вы можете переместиться в соседнюю клетку или остаться на месте. Как только вы достигаете $N$, цель считается достигнутой.

Если существует способ добраться до клетки $N$, не потерпев неудачу, выведите минимально возможное время. Если такого способа не существует, выведите -1.

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

В первой строке дано число $N$ — длина числовой прямой $(1 \le N \le 2 \times 10^5)$.

Во второй строке дано общее время контроля $T$ $(1 \le T \le 2 \times 10^5)$.

С третьей строки следуют $T$ строк, каждая из которых содержит два целых числа $l_t$ и $r_t$, разделенных пробелом $(1 \le l_t \le r_t \le N)$.

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

Выведите минимальное время. Если достичь цели невозможно, выведите -1.

Примеры

Input 1

4
4
2 4
1 1
2 2
3 3

Output 1

4

Input 2

5
3
2 5
3 4
1 4

Output 2

-1