B. Вулканы
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Яхуб потерялся в огромной пустыне. Пустыня представляет собой квадратную матрицу размера n × n, каждая ячейка матрицы — это часть пустыни. Будем считать, что ячейка (i, j) — это ячейка на пересечении строки i и столбца j матрицы (1 ≤ i, j ≤ n). Из ячейки пустыни (i, j) Яхуб может пойти либо вниз, либо направо, то есть, в ячейку (i + 1, j), либо (i, j + 1).

Известно, что в m ячейках пустыни находятся вулканы. Конечно, Яхуб не может заходить на такие ячейки.

Изначально Яхуб стоит в ячейке (1, 1). Ему надо дойти до ячейки (n, n). Зная, что для единичного перехода из одной ячейки в другую Яхубу требуется ровно 1 секунда, найдите минимальное время, за которое он может прибыть в ячейку (n, n).

Входные данные

В первой строке содержатся два целых числа, n (1 ≤ n ≤ 109) и m (1 ≤ m ≤ 105). В каждой из следующих m строк содержится пара целых чисел, x и y (1 ≤ x, y ≤ n), обозначающих координаты вулканов.

Считайте, что строки матрицы пронумерованы от 1 до n сверху вниз, а столбы от 1 до n слева направо. Гарантируется, что в ячейке (1, 1) нет вулкана. Никакие два вулкана не находятся в одной позиции.

Выходные данные

Выведите единственное целое число, минимальное время, за которое Яхуб сможет прибыть в ячейку (n, n). Если решения не существует (Яхуб не может прийти в конечную ячейку), выведите -1.

Примеры
Входные данные
4 2
1 3
1 4
Выходные данные
6
Входные данные
7 8
1 6
2 6
3 5
3 6
4 3
5 1
5 2
5 3
Выходные данные
12
Входные данные
2 2
1 2
2 1
Выходные данные
-1
Примечание

Рассмотрим первый тестовый пример. Один из возможных путей: (1, 1)  →  (1, 2)  →  (2, 2)  →  (2, 3)  →  (3, 3)  →  (3, 4)  →  (4, 4).