Description

Sally Snail likes to wander on an $N \times N$ board ($1<n \le 120$).

She always starts in the upper-left corner. The board has empty cells (denoted by \verb!.!) and $B$ obstacles (denoted by \verb!#!).

Here is an example board in this notation:

$$\boxed{\quad\begin{aligned} \verb! A B C D E F G H! \\ \verb!1 S . . . . . # .! \\ \verb!2 . . . . # . . .! \\ \verb!3 . . . . . . . .! \\ \verb!4 . . . . . . . .! \\ \verb!5 . . . . . # . .! \\ \verb!6 # . . . . . . .! \\ \verb!7 . . . . . . . .! \\ \verb!8 . . . . . . . .! \\ \end{aligned}\quad}$$

Sally always moves vertically (up or down) or horizontally (left or right). From the starting cell (always denoted as $\tt A1$), she may move either down or right. Once Sally chooses a direction, she continues in that direction. If she encounters the edge of the board or an obstacle, she stops and turns $90$ degrees. She cannot leave the board or enter an obstacle. Also, Sally never crosses a cell she has already visited. When she can no longer move, she stops.

Here is a trace of one walk on the board above:

$$\boxed{\quad\begin{aligned} \verb! A B C D E F G H! \\ \verb!1 S--------------+ # .! \\ \verb!2 . . . . # | . .! \\ \verb!3 . . . . . | . .! \\ \verb!4 . . . . . +-----+! \\ \verb!5 . . . . . # . |! \\ \verb!6 # . . . . . . |! \\ \verb!7 +-----------------+ |! \\ \verb!8 +--------------------+! \\ \end{aligned}\quad}$$

She goes right, then down, right, down, then left, up, and finally right. At that point she encounters a cell she has already visited, so she stops. However, if after hitting the obstacle at $\tt F5$ she had chosen the other way — namely, turned to what looks like the left to us — the result would be different.

Your task is to compute and output the maximum number of cells Sally can visit if she chooses her path optimally.

Input Format

The first line contains $N$ — the size of the board, and $B$ — the number of obstacles ($1 \le B \le 200$). The next $B$ lines contain the positions of the obstacles. The sample input below corresponds to the example board above. The sample output below shows the answer to that instance. Note that when $N > 26$, the input file cannot denote obstacles beyond column Z. (You do not need to worry specifically about this — just continue from the ASCII code of A; whatever letters come next are fine.)

Output Format

Output a single line with the maximum number of cells Sally can visit.

8 4
E2
A6
G1
F5

33

Hint

$$\boxed{\quad\begin{aligned} \verb! A B C D E F G H! \\ \verb!1 S . . . . . # .! \\ \verb!2 | . . . # . . .! \\ \verb!3 | . . . +--------+! \\ \verb!4 | . . . | . . |! \\ \verb!5 +-----------+ # . |! \\ \verb!6 # . . . . . . |! \\ \verb!7 +------------------ |! \\ \verb!8 +--------------------+! \\ \end{aligned}\quad}$$

Translation from NOCOW.

USACO Training Section 5.2.

This problem may contain issues; we do not guarantee that there exists a program that can pass all inputs that meet the requirements. If you believe your solution can pass all valid inputs, feel free to contact the administrators.

Translated by ChatGPT 5