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 ≤ 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. 

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.

Examples

Input

4 2
1 3
1 4


Output

6


Input

7 8
1 6
2 6
3 5
3 6
4 3
5 1
5 2
5 3


Output

12


Input

2 2
1 2
2 1


Output

-1

Note

Consider the first sample. A possible road is: (1, 1) →  (1, 2) →  (2, 2) →  (2, 3) →  (3, 3) →  (3, 4) →  (4, 4).
import java.util.*;
import java.io.*;

public class B2 {
    public static long time = 0;

    public static void main(String[] args) throws Exception {
        time = System.currentTimeMillis();
        solve();
        out.flush();
    }

    public static void solve() throws Exception {
        int n1 = ni();
        
        int k1 = ni();
        int[][] points = new int[k1][2];
        int[] cand = new int[k1 * 2];
        for (int i =0; i < k1; i++){
            points[i][0] = ni() - 1;
            points[i][1] = ni() - 1;
            cand [i << 1] = points[i][0];
            cand [(i << 1) + 1] = points[i][0] + 1;
            if (points[i][0] == n1 - 1) cand [(i << 1) + 1] = points[i][0];
        }
        IntL importantPoints = Arrayz.sortedUnique(cand);
        IntL[] al = new IntL[importantPoints.size];
        for (int i =0 ; i < al.length; i++){
            al[i] = new IntL();
        }
        for (int [] e: points){
            int id = importantPoints.binarySearch(e[0]);
            al[id].add(e[1]);
        }
        for (IntL e: al){
            e.sort();
        }
        
        ArrayList<int[]> curGoodSeg = new ArrayList();
        if (importantPoints.get(0) == 0){
            curGoodSeg.add(new int[]{0 , al[0].get(0) - 1});
        }
        else {
            curGoodSeg.add(new int[]{0 , n1 - 1});
        }
        for (int rowNo = 0; rowNo < importantPoints.size; rowNo++){
            ArrayList<int[]> curSegs = new ArrayList<>();
            int ptr1 = 0;
            int curStart = 0;
            for (;;){
                if (ptr1 >= al[rowNo].size) break;
                if (curStart == al[rowNo].get(ptr1)){
                    ptr1++;
                    curStart++;
                }
                else break;
            }
            for (;;){
                if (curStart >= n1) break;
                if (ptr1 == al[rowNo].size){
                    curSegs.add(new int[]{curStart, n1 - 1});
                    break;
                }
                else {
                    int end = al[rowNo].get(ptr1);
                    curSegs.add(new int[]{curStart, end - 1});
                    curStart = end + 1;
                    ptr1++;
                    for (;;){
                        if (ptr1 >= al[rowNo].size) break;
                        if (curStart == al[rowNo].get(ptr1)){
                            ptr1++;
                            curStart++;
                        }
                        else break;
                    }
                }
            }
//          p2(curSegs);
            
            ArrayList<int[]> nextGoodSeg = new ArrayList();
            int segPtr = 0;
            A:
            for (int[] e: curGoodSeg){
                for (;;){
                    if (segPtr >= curSegs.size()){
                        break A;
                    }
                    int[] curCand = curSegs.get(segPtr);
                    if (curCand[START] > e[END]){
                        continue A;
                    }
                    else {
                        int maxStart = Math.max(e[START],curCand[START]);
                        int minEnd = Math.min(e[END],curCand[END]);
                        if (minEnd >= maxStart){
                            nextGoodSeg.add(new int[]{maxStart,curCand[END]});
                        }
                        segPtr++;
                    }
                }
            }
            curGoodSeg = nextGoodSeg;
        }
        for (int[] e: curGoodSeg){
            if (e[START] <= n1 -1 
                    && e[END] >= n1 - 1
                    ){
                pn(n1 * 2 - 2);
                return;
            }
        }
        pn(-1);

    }
    static int START = 0;
    static int END = 1;
    static void p2(ArrayList<int[]> l1){
        for (int[] e: l1){
            System.out.print(Arrays.toString(e)+" ");
        }
        System.out.println();
    }

    public static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    public static StringTokenizer st = null;

    public static String nx() throws Exception {
        for (; st == null || !st.hasMoreTokens();) {
            String k1 = in.readLine();
            if (k1 == null) return null;
            st = new StringTokenizer(k1);
        }
        return st.nextToken();
    }

    public static int ni() throws Exception {
        return Integer.parseInt(nx());
    }

    public static long nl() throws Exception {
        return Long.parseLong(nx());
    }

    public static double nd() throws Exception {
        return Double.parseDouble(nx());
    }

    public static void px(Object... l1) {
        System.out.println(Arrays.deepToString(l1));
    }

    public static boolean FLUSH = false;
    public static PrintWriter out = new PrintWriter(System.out, FLUSH);

    public static void p(Object... l1) {
        for (int i = 0; i < l1.length; i++) {
            if (i != 0) out.print(' ');
            out.print(l1[i].toString());
        }
    }

    public static void pn(Object... l1) {
        for (int i = 0; i < l1.length; i++) {
            if (i != 0) out.print(' ');
            out.print(l1[i].toString());
        }
        out.println();
    }

    public static void pn(Collection l1) {
        boolean first = true;
        for (Object e : l1) {
            if (first) first = false;
            else out.print(' ');
            out.print(e.toString());
        }
        out.println();
    }

    private static class IntL implements Iterable<Integer> {
        public int[] cont = null;
        public int size = 0;

        public IntL(int initialCapacity) {
            this.cont = new int[initialCapacity];
        }

        public IntL() {
            this(5);
        }

        public void add(int e) {
            if (size == cont.length) {
                cont = Arrays.copyOf(cont, ((cont.length * 3) >> 1) + 1);
            }
            cont[size++] = e;
        }

        public int get(int id) {
            if (id >= 0) return cont[id];
            else return cont[size + id];
        }

        public void sort() {
            Shuffle.ints(cont, 0, size);
            Arrays.sort(cont, 0, size);
        }

        public int binarySearch(int v1) {
            return Arrays.binarySearch(cont, 0, size, v1);
        }

        @Override
        public String toString() {
            StringBuilder fin = new StringBuilder();
            fin.append('{');
            for (int i = 0; i < size; i++) {
                if (i != 0) fin.append(", ");
                fin.append(cont[i]);
            }
            fin.append('}');
            return fin.toString();
        }

        @Override
        public Iterator<Integer> iterator() {
            return new It();
        }

        public class It implements Iterator<Integer> {
            int ptr = 0;

            @Override
            public boolean hasNext() {
                if (ptr < size) return true;
                return false;
            }

            @Override
            public Integer next() {
                int fin = cont[ptr];
                ptr++;
                return fin;
            }

            @Override
            public void remove() {}
        }
    }

    private static class Arrayz {
        public static IntL sortedUnique(int[] l1) {
            int[] copy = l1.clone();
            Arrays.sort(copy);
            IntL fin = new IntL();
            for (int i = 0; i < copy.length; i++) {
                if (i == 0) {
                    fin.add(copy[i]);
                    continue;
                }
                if (copy[i] != copy[i - 1]) {
                    fin.add(copy[i]);
                }
            }
            return fin;
        }
    }

    private static class Shuffle {
        private static Random r1 = new Random();

        public static void ints(int[] l1, int n1, int n2) {
            for (int i = 0; i < n2 - n1; i++) {
                int k1 = i + r1.nextInt(n2 - n1 - i);
                int temp = l1[i + n1];
                l1[i + n1] = l1[k1 + n1];
                l1[k1 + n1] = temp;
            }
        }
    }

}
