Змійка
"Змійка" - це аркадна комп'ютерна гра, яка ведеться на квадратному полі NxN, розбитому на квадрати 1x1. Рядки поля пронумеровано від 1 до N зверху донизу, а стовбці - від 1 до N зліва праворуч. Кожній клітинці поля можна поставити у відповідність її координати (r, c), де r - це номер рядка, у якому вона знаходиться, а c - номер стовбця.
У довільний момент гри змійка займає деяку послідовність квадратів поля таку, що два сусідніх у цій послідовності квадрати мають спільну сторону. У першому квадраті послідовності заходиться хвіст змійки, а у останньому - її голова. На початку і хвіст, і голова змійки знаходяться у клітинці з координатами (1, 1), а у кожній з інших клітинок є або ягідка, або грибок.
За один хід змійка може перемістити голову у одному з 4-х напрямків - угору, ліворуч, праворуч, донизу. Якщо сусіднього квадрату у напрямку хода не існує або, якщо у цьому квадраті знаходиться грибок або сама змійка, то вона гине і гра завершується. Якщо ж у цьому квадраті знаходиться ягідка, то змійка з'їдає її і збільшує за рахунок цього свою довжину на один квадрат. Нехай, наприклад, у деякий момент гри змійка розміщена наступним чином:
Тоді при ході вверх і вниз змійка гине, так як попаде у клітинку з власним тулубом. При ході праворуч змійка також гине, так як попаде у клітинку з грибком. Єдиний хід, при якому змійка не загине - ліворуч. Після цього ходу вона буде розміщуватись наступним чином:
Мета гравця - керувати змвйкою так, щоб, перед тим як загинути, вона набула якомога більшої довжини. Школяру Васі грати у "Змійку" самому не цікаво, тому він розробив алгоритм керування змійкою. Перший хід, згідно алгоритму Васі, змійка робить праворуч, якщо праворуч від неї немає грибка, і вниз - у іншому випадку (якщо знизу є грибок, то після першого ходу змійка гине). Далі, у довільний момент гри, змійка пам'ятає напрям, у якому вона робила попередній хід, і на наступному ході намагається зробити хід у тому ж напрямку. Якщо це призводить до негайної загибелі, то змійка змінює напрям руху, повертаючись на 90 градусів за годинниковою стрілкою, і робить хід у новому напрямку (навіть якщо це призводить до її негайної загибелі).
Нахай наприклад, поле для гри у "Змійку" на початку виглядає наступним чином:
Тоді змійка, рухаючись за алгоритмом Васі, безпосередньо перед тим, як загинути, розмістиьтся так, як показано на рисунку:
Вася розуміє, що розроблений ним алгоритм - не оптимальний. Наприклад, на рисунку вище змійка цілком могла б далі піти праворуч і збільшити свою довжину, а, діючи по Васиному алгоритму, вона роюить хід ліворуч і гине. Тим не менше, Васі здається, що його алгоритм - дуже добрий і дозволяє змійці досягнути дуже великої довжини.
Допоможіть Васі перевірити цю гіпотезу, написавши програму, яка моделює роботу його алгоритму. Програма отримує на вхід розмір поля N і розміщення всіх грибків, і знаходить, скілько квадратів буде займати змійка безпосередньо перед тем, як загинути, якщо вона буде рухатись за алгоритмом Васі.
Вхідні дані
В первой строке задано целое число N (2 ≤ N ≤ 40000) - размер поля. Во второй - количество грибков K (0 ≤ K ≤ 100), последующие K строк содержат координаты X грибков, далее следует опять число K и в последних K строках - координаты Y соответствующих грибков. Гарантируется, что никаких два грибка не расположены в одной клетке и в клетке (1, 1) нет грибка.
Вихідні дані
Єдине ціле число, рівне кількості квадратів, які займає змійка безпосередньо перед ходом, на якому вона гине, у припущенні, що змійка рухається згідно алгоритму Васі.