問題文

コウメ市には $1, 2, \dots, N$ の番号が付いた $N$ 個の町があり、
これらは次に示す $(N - 1)$ 本の「地下道」と $M$ 本の「近道」で一方向に結ばれています。

• $i$ $(1 \leq i \leq N - 1)$ 本目の「地下道」は町 $i$ と町 $(i + 1)$ をこの順に結び、その間の距離は $2$ である。

• $j$ $(1 \leq j \leq M)$ 本目の「近道」は町 $A_{j}$ と町 $B_{j}$ $(A_{j} < B_{j})$ をこの順に結び、その間の距離は $(2 B_{j} - 2 A_{j} - 1)$ である。

これら $(N + M - 1)$ 本の道のみを通過して町 $1$ から町 $N$ まで移動するとき、最短移動距離を求めてください。

制約

• $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)$

• 入力はすべて整数

入力

入力は次の形式で与えられます。

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

• $1$ 行目には $N$ と $M$ がこの順に半角スペース区切りで与えられる

• $(1 + i)$ $(1 \leq i \leq M)$ 行目には $A_{i}$ と $B_{i}$ がこの順に半角スペース区切りで与えられる

出力

答えを $1$ 行に出力し、最後に改行してください。

サンプル

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