← 返回题目列表

Codeforces · 383/B

B. 火山

中文机器翻译题面 查看原题

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)。