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<sup class="upper-index">9</sup>) and *m* (1 ≤ *m* ≤ 10<sup class="upper-index">5</sup>). 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.
#!python

import fileinput
import heapq
from collections import defaultdict

class B:
    def __init__(self, input):
        self.n, self.m = map(int, input.readline().split())
        # self.map = [[True]*self.n]*self.n
        # read coord of volcanoes
        self.vols = set()
        for ind in input:
            i, j = map(int, ind.split())
            self.vols.add((i-1, j-1))
        # print(self.vols)

    def h(self, s, e):
        return abs(s[0]-e[0]) + abs(s[1] - e[1])

    def neighbor(self, p):
        return [(p[0]+1, p[1]) if p[0] < self.n-1 and (p[0]+1, p[1]) not in self.vols else None,
                (p[0], p[1]+1) if p[1] < self.n-1 and (p[0], p[1]+1) not in self.vols else None]

    def AStar(self, start, goal):
        openset = [] # priority queue
        closedset = {start}
        g = defaultdict(lambda : float('inf'))
        g[start] = 0
        heapq.heappush(openset, (g[start] + self.h(start, goal), start))

        while any(openset):
            dis, cur = heapq.heappop(openset)
            if (cur == goal):
                return dis
            for nei in self.neighbor(cur):
                if (nei is None or nei in closedset): continue
                gt = g[cur] + 1;
                if (gt < g[nei]):
                    g[nei] = gt
                    heapq.heappush(openset, (gt + self.h(nei, goal), nei))

        return -1

    def solve(self):
        return self.AStar((0,0), (self.n-1,self.n-1))

if __name__ == "__main__":
    b = B(fileinput.input())
    print(b.solve())
