Problem Description

There is a square matrix with $n$ rows and $n$ columns, each containing $n$ cells. Each cell contains a number, initially set to $0$. There are $m$ modifications, each incrementing the number in a specific cell by $1$.

A step operation is defined as decrementing the number in a non-zero cell by $1$ and incrementing the number in another cell (which can be $0$) by $1$.

Determine the minimum number of operations required to make all numbers in the cells either $0$ or $1$, with all $1$s forming a rectangle. Output the number of operations.

Input Format

The first line contains two integers, representing the number of rows and columns of the square matrix $n$ and the number of modifications $m$.

The next $m$ lines each contain two integers $x, y$, indicating that the number in the cell at row $x$ and column $y$ is incremented by $1$.

Output Format

Output a single integer, representing the answer.

Sample Input and Output

Sample Input #1

3 2
1 1
1 1

Sample Output #1

1

Sample Input #2

4 3
2 2
4 4
1 1

Sample Output #2

2

Sample Input #3

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

Sample Output #3

3

Notes

Sample Explanation

Sample 1 Explanation

Decrement the cell at row $1$ and column $1$ by $1$, and increment the cell at row $2$ and column $1$ by $1$.

Sample 3 Explanation

• Decrement the cell at row $2$ and column $3$ by $1$, and increment the cell at row $3$ and column $3$ by $1$.
• Decrement the cell at row $4$ and column $2$ by $1$, and increment the cell at row $2$ and column $5$ by $1$.
• Decrement the cell at row $4$ and column $4$ by $1$, and increment the cell at row $3$ and column $5$ by $1$.

Data Constraints

For all test cases, the following constraints apply:

• $1 \leq n \leq 100$, $1 \leq m \leq n^2$.
• $1 \leq x, y \leq n$.
• The input data guarantees a solution exists.

Notes

Translated from COCI2008-2009 CONTEST #6 T3 NERED, translated by @一扶苏一.

见题面 Input 部分

见题面 Output 部分