Змейка
"Змейка" - это аркадная компьютерная игра, которая ведется на квадратном поле 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) нет грибка.
Выходные данные
Единственное целое число, равное количеству квадратов, занимаемых змейкой непосредственно перед ходом, на котором она погибнет, в предположении, что змейка двигается согласно алгоритму Васи.