長さ $N-1$ の数直線がある。数直線上の $1$ から出発し、$N$ に最短時間で到達することを目指す。合計 $T$ 分間、毎分ごとに規制が発生する。

$t$ 分目の規制は2つの整数 $l_t, r_t$ で与えられ、$t+0.5$ 分の時点であなたの位置 $x$ が $l_t \le x \le r_t$ を満たしていると、即座に失敗となる。$T < t$ の場合は規制は発生しない。

毎分、隣接するマスに移動するか、現在のマスに留まることができる。$N$ に到達した時点で目標達成となる。

失敗せずに $N$ に到達する方法が存在するならば可能な最短時間を、存在しないならば -1 を出力せよ。

制約

1行目に数直線の長さ $N$ が与えられる。$(1 \le N \le 2 \times 10^5)$

2行目に規制が発生する合計時間 $T$ が与えられる。$(1 \le T \le 2 \times 10^5)$

3行目から $T$ 行にわたり、各行に2つの整数 $l_t, r_t$ が空白区切りで与えられる。$(1 \le l_t \le r_t \le N)$

入出力例

入力 1

4
4
2 4
1 1
2 2
3 3

出力 1

4

入力 2

5
3
2 5
3 4
1 4

出力 2

-1