Mamy linię prostą o długości $N-1$. Celem jest dotarcie z punktu $1$ do punktu $N$ w jak najkrótszym czasie. W ciągu $T$ minut, w każdej minucie następuje kontrola.

Kontrola w minucie $t$ jest określona przez dwie liczby całkowite $l_t$ oraz $r_t$. Jeśli w momencie $t+0.5$ Twoja pozycja $x$ spełnia warunek $(l_t \le x \le r_t)$, natychmiast przegrywasz. Jeśli $t > T$, żadna kontrola nie występuje.

W każdej minucie możesz przemieścić się do sąsiedniego pola lub pozostać w miejscu. Osiągnięcie punktu $N$ oznacza natychmiastowy sukces.

Jeśli istnieje sposób na dotarcie do punktu $N$ bez przegranej, wypisz minimalny czas potrzebny na osiągnięcie celu. W przeciwnym razie wypisz -1.

Wejście

W pierwszej linii podana jest długość linii prostej $N$ $(1 \le N \le 2 \times 10^5)$.

W drugiej linii podany jest całkowity czas trwania kontroli $T$ $(1 \le T \le 2 \times 10^5)$.

W kolejnych $T$ liniach podane są dwie liczby całkowite $l_t$ oraz $r_t$ oddzielone spacją, określające zakres kontroli w minucie $t$ $(1 \le l_t \le r_t \le N)$.

Wyjście

Wypisz minimalny czas. Jeśli dotarcie do celu jest niemożliwe, wypisz -1.

Przykład

Wejście 1

4
4
2 4
1 1
2 2
3 3

Wyjście 1

4

Wejście 2

5
3
2 5
3 4
1 4

Wyjście 2

-1