P6469 [COCI 2008/2009 #6] NERED

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.

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 one line with one integer, the answer.

#### 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](https://hsin.hr/coci/archive/2008_2009/) [CONTEST #6](https://hsin.hr/coci/archive/2008_2009/contest6_tasks.pdf) *T3 NERED***. Translation by @[一扶苏一](https://www.luogu.com.cn/user/65363). Translated by ChatGPT 5