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 ≤ 109) and m(1 ≤ m ≤ 105). 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.

备注:

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