Яхуб потерялся в огромной пустыне. Пустыня представляет собой квадратную матрицу размера 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, n). Если решения не существует (Яхуб не может прийти в конечную ячейку), выведите -1.
Примечание
Рассмотрим первый тестовый пример. Один из возможных путей: (1, 1) → (1, 2) → (2, 2) → (2, 3) → (3, 3) → (3, 4) → (4, 4).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 2
1 3
1 4
|
6
|
|
2
|
7 8
1 6
2 6
3 5
3 6
4 3
5 1
5 2
5 3
|
12
|
|
3
|
2 2
1 2
2 1
|
-1
|