Snake
"Snake" is a classic arcade game played on a square grid of size NxN, where each cell measures 1x1. The grid's rows are numbered from 1 to N from top to bottom, and columns are numbered from 1 to N from left to right. Each cell can be identified by its coordinates (r, c), where r is the row number and c is the column number.
During the game, the snake occupies a sequence of adjacent squares, where each pair of consecutive squares shares a side. The snake's tail is at the first square of this sequence, and its head is at the last. Initially, both the tail and the head are at the cell (1, 1). All other cells contain either a berry or a mushroom.
The snake can move its head in one of four directions: up, down, left, or right. If the snake attempts to move into a non-adjacent square, or into a square containing a mushroom or part of its own body, it dies and the game ends. If the snake moves into a square with a berry, it eats the berry and grows by one square. For example, consider the following snake position:
In this scenario, moving up or down results in death as the snake would collide with its own body. Moving right also results in death due to a mushroom. The only safe move is to the left, after which the snake appears as follows:
The objective is to control the snake to achieve the maximum possible length before it dies. Vasya, a schoolboy, finds playing "Snake" alone dull, so he created an algorithm to control the snake. According to Vasya's algorithm, the snake first moves right if there is no mushroom to the right; otherwise, it moves down (if there is a mushroom below, the snake dies on the first move). Thereafter, the snake tries to continue in the same direction as its last move. If this results in immediate death, it turns 90 degrees clockwise and moves in the new direction, even if this leads to death.
For instance, consider the initial field configuration:
Following Vasya's algorithm, the snake will be positioned as shown just before it dies:
Vasya acknowledges that his algorithm isn't optimal. For example, in the scenario above, the snake could have moved further right to grow longer, but following Vasya's algorithm, it turns left and dies. Despite this, Vasya believes his algorithm is effective and allows the snake to reach a significant length.
Help Vasya test his hypothesis by writing a program that simulates his algorithm. The program should take the field size N and the positions of all mushrooms as input and determine how many squares the snake occupies just before the move that leads to its death, assuming it follows Vasya's algorithm.
Input
The first line contains an integer N (2 ≤ N ≤ 40000) - the size of the field. The second line contains the number of mushrooms K (0 ≤ K ≤ 100). The next K lines list the X coordinates of the mushrooms, followed by another K lines listing the Y coordinates of the corresponding mushrooms. It is guaranteed that no two mushrooms share the same cell and there is no mushroom at (1, 1).
Output
Output a single integer representing the number of squares occupied by the snake just before the move that results in its death, assuming it follows Vasya's algorithm.