有一條長度為 $N-1$ 的數線。目標是從數線上的 $1$ 出發，以最短時間抵達 $N$。總共有 $T$ 分鐘，每一分鐘都會發生一次管制。

第 $t$ 分鐘的管制由兩個整數 $l_t, r_t$ 給出，若在第 $t+0.5$ 分鐘時，你的位置 $x$ 滿足 $(l_t \le x \le r_t)$，則會立即失敗。若 $T < t$，則不會發生任何管制。

每一分鐘，你可以移動到相鄰的格子，或是停留在當前位置。一旦抵達 $N$ 即視為成功。

若存在不失敗並抵達 $N$ 的方法，請輸出最短所需時間；若不存在，則輸出 -1。

輸入格式

第一行給出數線長度 $N$。$(1 \le N \le 2 \times 10^5)$

第二行給出發生管制的總時間 $T$。$(1 \le T \le 2 \times 10^5)$

從第三行開始，共 $T$ 行，每行給出兩個整數 $l_t, r_t$，以空白分隔。$(1 \le l_t \le r_t \le N)$

輸出格式

輸出最短時間。若不存在則輸出 -1。

範例

範例輸入 1

4
4
2 4
1 1
2 2
3 3

範例輸出 1

4

範例輸入 2

5
3
2 5
3 4
1 4

範例輸出 2

-1