Задача 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