Il existe une ligne droite de longueur $N-1$. L'objectif est de partir de $1$ et d'atteindre $N$ le plus rapidement possible. Il y a des contrôles qui surviennent chaque minute pendant un total de $T$ minutes.

Le contrôle à la minute $t$ est donné par deux entiers $l_t$ et $r_t$. Si, à la minute $t+0.5$, votre position $x$ satisfait la condition $(l_t \le x \le r_t)$, vous échouez immédiatement. Si $t > T$, aucun contrôle n'a lieu.

À chaque minute, vous pouvez vous déplacer vers une case adjacente ou rester sur votre position actuelle. Vous réussissez l'objectif dès que vous atteignez $N$.

Si une méthode permet d'atteindre la case $N$ sans échouer, affichez le temps minimal nécessaire ; sinon, affichez -1.

Entrée

La première ligne contient la longueur de la ligne droite $N$. $(1 \le N \le 2 \times 10^5)$

La deuxième ligne contient le temps total pendant lequel les contrôles surviennent $T$. $(1 \le T \le 2 \times 10^5)$

À partir de la troisième ligne, $T$ lignes suivent, chacune contenant deux entiers $l_t$ et $r_t$ séparés par un espace. $(1 \le l_t \le r_t \le N)$

Sortie

Affichez le temps minimal. Si cela est impossible, affichez -1.

Exemples

Entrée 1

4
4
2 4
1 1
2 2
3 3

Sortie 1

4

Entrée 2

5
3
2 5
3 4
1 4

Sortie 2

-1