Задача Container. Вы - капитан корабля. В трюме, имеющем форму квадрата размера N*N, Вы перевозите контейнеры размером 1*1*2. Эти контейнеры нельзя передвигать, но можно кантовать (т.е. перекатывать относительно ребра, которое находится на полу), как показано на рисунке (вид сверху). На кантование контейнера тратится одна минута. Сначала все контейнеры касаются пола стороной 1*1. Расстояние от ребра каждого контейнера до стены - всегда целое число. Кроме первого, другие контейнеры остаются на месте. Нельзя ставить контейнер на другой. Нельзя, чтобы контейнер выходил за границы трюма, но он может касаться стены. За сколько минут Вы сможете перекантовать первый контейнер в заданную ячейку так, чтобы он касался пола стороной 1*1?
|
До кантования |
||||||||||||||||
|
После кантования |
||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Технические условия. Программа Container считывает с клавиатуры (устройства стандартного ввода) два целых числа - размер трюма N (3≤N≤1000) и количество контейнеров M (1≤M≤N*N–2). Далее программа читает M+1пару чисел x,y - координаты контейнеров и координаты ячейки, в которую необходимо поставить первый контейнер. Все ячейки различны. Программа выводит на экран искомое минимальное время. Если перекантовать контейнер невозможно, выводите -1.
Примеры
Ввод
4 1 1 1 4 4
Вывод
4
Ввод
6 3 3 2 4 4 4 5 1 1
Вывод
7
Ввод
7 5 4 4 4 5 4 3 3 4 5 4 1 1
Вывод
-1