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*)$.

Input

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.

Output

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.

Note

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