Iahub 在一片非常大的沙漠中迷路了。沙漠可以表示为一个 n × n 方阵,其中每个单元格都是沙漠的一个区域。单元格 (i, j) 表示第 i 行 j 列的单元格 (1 ≤ i, j ≤ n)。 Iahub 只能从一个单元格 (i, j) 向下或向右,即到单元格 (i + 1, j) 或 (i, j + 1)。
另外,还有 m 个单元格被火山占据,Iahub 无法进入。
Iahub 最初位于单元格 (1, 1),他需要前往单元格 (n, n)。已知 Iahub 从一个单元格移动到另一个单元格需要 1 秒,求他到达单元格 (n, n) 的最短时间。
输入
第一行包含两个整数 n (1 ≤ n ≤ 109) 和 m (1 ≤ m ≤ 105)。接下来的 m 行中的每一行都包含一对整数 x 和 y (1 ≤ x, y ≤ n),表示火山的坐标。
考虑矩阵行从上到下从 1 到 n 编号,矩阵列从左到右从 1 到 n 编号。单元格 (1, 1) 中没有火山。没有两座火山占据相同的位置。
输出
打印一个整数,即 Iahub 到达单元 (n, n) 的最短时间。如果不存在解(没有到达最终单元格的路径),则打印 -1。
示例
输入 #1
4 2 1 3 1 4
输出 #1
6
输入 #2
7 8 1 6 2 6 3 5 3 6 4 3 5 1 5 2 5 3
输出 #2
12
输入 #3
2 2 1 2 2 1
输出 #3
-1
注意
考虑第一个样本。一条可能的道路是:(1, 1) → (1, 2) → (2, 2) → (2, 3) → (3, 3) → (3, 4) → (4, 4)。