Volcanoes

题意翻译

Iahub 在一片沙漠中迷路了。 沙漠是一片 $n\times n$ 的网格，里面有 $m$ 座火山，第 $i$ 座火山位于 $(x_i,y_i)$，保证没有火山位于 $(1,1)$，没有两座火山位于同一个位置。 Iahub 在 $(1,1)$，他要去 $(n,n)$。在每一秒，他可以从 $(x,y)$ 走到 $(x+1,y)$ 或者 $(x,y+1)$。但是他不能走进火山。 请你告诉 Iahub 他需要多少秒才能到达目的地。如果他无论如何也到达不了，输出 $-1$。 $1\le x_i,y_i\le n\le 10^9,1\le m\le 10^5$

题目描述

Iahub got lost in a very big desert. The desert can be represented as a $ n×n $ square matrix, where each cell is a zone of the desert. The cell $ (i,j) $ represents the cell at row $ i $ and column $ j $ $ (1<=i,j<=n) $ . Iahub can go from one cell $ (i,j) $ only down or right, that is to cells $ (i+1,j) $ or $ (i,j+1) $ . Also, there are $ m $ cells that are occupied by volcanoes, which Iahub cannot enter. Iahub is initially at cell $ (1,1) $ and he needs to travel to cell $ (n,n) $ . Knowing that Iahub needs $ 1 $ second to travel from one cell to another, find the minimum time in which he can arrive in cell $ (n,n) $ .

输入输出格式

输入格式

The first line contains two integers $ n $ $ (1<=n<=10^{9}) $ and $ m $ $ (1<=m<=10^{5}) $ . Each of the next $ m $ lines contains a pair of integers, $ x $ and $ y $ $ (1<=x,y<=n) $ , representing the coordinates of the volcanoes. Consider matrix rows are numbered from 1 to $ n $ from top to bottom, and matrix columns are numbered from 1 to $ n $ from left to right. There is no volcano in cell $ (1,1) $ . No two volcanoes occupy the same location.

输出格式

Print one integer, the minimum time in which Iahub can arrive at cell $ (n,n) $ . If no solution exists (there is no path to the final cell), print -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

说明

Consider the first sample. A possible road is: $ (1,1) $ $ → $ $ (1,2) $ $ → $ $ (2,2) $ $ → $ $ (2,3) $ $ → $ $ (3,3) $ $ → $ $ (3,4) $ $ → $ $ (4,4) $ .