P1448 [NOI1998] Scarf Cutting

NOI1998 Day 2 T1.

A tailor has a very precious silk scarf. Unfortunately, some parts of the scarf have been eaten by moths. The tailor certainly does not want to throw it away, so he plans to cut the scarf into two small scarves for his two daughters. Naturally, the larger the sum of the areas of the two small scarves, the better. The scarf is an equilateral triangle, and each of its three sides is evenly divided into $N$ segments, that is, the equilateral triangle is evenly divided into $N^2$ cells, each of which is an equilateral triangle of area $1$. As shown in the figure for $N=5$, the shaded cells represent the parts eaten by moths. From top to bottom, the scarf is divided into $N$ rows: - The first row has $1$ cell. - The second row has $3$ cells, among which $2$ are of the shape $\Delta$ and $1$ is of the shape $\nabla$ (we consider these two triangles to be the same shape). - The third row has $5$ cells, among which $3$ are of the shape $\Delta$ and $2$ are of the shape $\nabla$, and so on. We use coordinates $(X, Y)$ to locate each cell. The cell in the first row has coordinates $(1, 1)$; for the second row, from left to right, the three cells have coordinates $(2, 1)$, $(2, 2)$, $(2, 3)$; and so on.  The cutting conditions for the scarf are as follows: 1. The two small scarves must be exactly the same shape as the original large scarf, i.e., equilateral triangles. 2. There must be no moth-eaten parts within either small scarf. 3. Cutting must follow the cell boundaries. 4. The total area of the two small scarves must be maximized. In the figure, the optimal cutting method has been drawn with bold lines, and the sum of areas is $4+9=13$. Now you need to write a program to help the tailor solve this problem.

- The first line contains an integer $N$ ($1 \leq N \leq 100$), indicating that the scarf is divided into $N^2$ cells in total. - The second line contains an integer $M$ ($1 \leq M \leq N^2 - 2$), indicating that $M$ cells of the scarf have been eaten by moths. - The next $M$ lines each contain two positive integers $X$ and $Y$, which are the coordinates of the $M$ moth-eaten cells. Adjacent items on the same line in the input file are separated by one or more spaces.

Output a single integer, the maximum total area of the two small scarves you can cut out.

- Sample explanation: As shown in the figure in the Description, the maximum total area of the two small scarves is $4+9=13$. - Constraints: - For $50\%$ of the testdata, $1 \leq N \leq 50$. - For $100\%$ of the testdata, $1 \leq N \leq 100$, $0 \leq M \leq N^2 - 2$, $1 \leq X \leq N$, $1 \leq Y \leq 2 \times N - 1$. The testdata are in Windows (CRLF) format. Translated by ChatGPT 5