Problem Statement

Koume City has $N$ towns numbered $1, 2, \dots, N$,
which are connected one-way by the $(N - 1)$ "underground roads" and $M$ "shortcuts" described below.

• The $i$-th $(1 \leq i \leq N - 1)$ "underground road" connects town $i$ and town $(i + 1)$ in this order, and the distance between them is $2$.

• The $j$-th $(1 \leq j \leq M)$ "shortcut" connects town $A_{j}$ and town $B_{j}$ $(A_{j} < B_{j})$ in this order, and the distance between them is $(2 B_{j} - 2 A_{j} - 1)$.

Find the shortest distance to travel from town $1$ to town $N$ using only these $(N + M - 1)$ roads.

Constraints

• $2 \leq N \leq 10^{9}$

• $\displaystyle 1 \leq M \leq \min \left( 10^{5}, \frac{ N \times (N - 1) }{ 2 } \right)$

• $1 \leq A_{i} < B_{i} \leq N$ $(1 \leq i \leq M)$

• $( A_{i}, B_{i} ) \neq ( A_{j}, B_{j} )$ $(1 \leq i < j \leq M)$

• All inputs are integers.

Input

The input is given in the following format.

$N$ $M$
$A_{1}$ $B_{1}$
$A_{2}$ $B_{2}$
   $\vdots$
$A_{M}$ $B_{M}$

• The $1$st line contains $N$ and $M$ in this order, separated by a space.

• The $(1 + i)$-th $(1 \leq i \leq M)$ line contains $A_{i}$ and $B_{i}$ in this order, separated by a space.

Output

Output the answer on $1$ line, followed by a newline.

Sample

10 5
1 6
2 4
2 7
4 6
6 9

15

2 1
1 2

1

1000000000 7
1 2
7 8
3 4
6 7
4 5
5 6
2 3

1999999991