Description

There is an $n \times n$ grid. Each row and each column has $n$ cells. Each cell contains a number, and initially all numbers are $0$. There are $m$ modifications, and each modification adds $1$ to the number in a specific cell.

Define one operation as decreasing the number in a non-zero cell by $1$, and increasing the number in another cell (which may be $0$) by $1$.

Find the minimum number of operations needed so that every cell contains either $0$ or $1$, and all cells with value $1$ form a rectangle. Output the number of operations.

Input Format

The first line contains two integers, representing the grid size $n$ and the number of modifications $m$.

The next $m$ lines each contain two integers $x, y$, meaning the number in the cell at row $x$, column $y$ is increased by $1$.

Output Format

Output one line with one integer, the answer.

3 2
1 1
1 1

1

4 3
2 2
4 4
1 1

2

5 8
2 2
3 2
4 2
2 4
3 4
4 4
2 3
2 3 

3

Hint

Sample Explanation

Explanation for Sample 1

Subtract $1$ from row $1$, column $1$, and add $1$ to row $2$, column $1$.

Explanation for Sample 3

• Subtract $1$ from row $2$, column $3$, and add $1$ to row $3$, column $3$.
• Subtract $1$ from row $4$, column $2$, and add $1$ to row $2$, column $5$.
• Subtract $1$ from row $4$, column $4$, and add $1$ to row $3$, column $5$.

Constraints

For all test points, it is guaranteed that:

• $1 \leq n \leq 100$, $1 \leq m \leq n^2$.
• $1 \leq x, y \leq n$.
• A solution always exists for the input.

Notes

This problem is translated from COCI2008-2009 CONTEST #6 T3 NERED. Translation by @一扶苏一.

Translated by ChatGPT 5