There is a number line of length $N-1$. The goal is to start at $1$ on the number line and reach $N$ in the shortest possible time. There are controls occurring every minute for a total of $T$ minutes.

The control at the $t$-th minute is given by two integers $l_t$ and $r_t$. If your position $x$ satisfies $l_t \le x \le r_t$ at time $t+0.5$, you fail immediately. If $t > T$, no controls occur.

Every minute, you can move to an adjacent cell or stay in your current cell. You succeed as soon as you reach $N$.

If there is a way to reach cell $N$ without failing, output the shortest time required; otherwise, output -1.

Input

The first line contains the length of the number line $N$. $(1 \le N \le 2 \times 10^5)$

The second line contains the total time $T$ during which controls occur. $(1 \le T \le 2 \times 10^5)$

From the third line, $T$ lines follow, each containing two integers $l_t$ and $r_t$ separated by a space. $(1 \le l_t \le r_t \le N)$

Output

Output the shortest time. If it does not exist, output -1.

Examples

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