题目描述

有一个方阵，方阵每行、每列均有 $n$ 个格子。每个格子上都有一个数，初始时均为 $0$。有 $m$ 次修改，每次会将某个格子上的数 $+1$。

定义一步操作为将某个非零格子上的数 $-1$，将另一个格子（可以为 $0$）上的数 $+1$。

请求出最小的操作步数，使得所有格子上的数均为 $0$ 或 $1$，且所有为 $1$ 的格子构成一个矩形。输出操作步数。

输入格式

第一行有两个整数，分别表示方阵的行列数 $n$ 和修改数 $m$。

接下来 $m$ 行，每行两个整数 $x, y$，表示将 $x$ 行 $y$ 列的格子上的数增加 $1$。

输出格式

输出一行一个整数，表示答案。

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

提示

【样例解释】

样例 1 解释

将第 $1$ 行第 $1$ 列减去 $1$，第 $2$ 行第 $1$ 列加上 $1$。

样例 3 解释

• 将第 $2$ 行第 $3$ 列减去 $1$，在第 $3$ 行第 $3$ 列加上 $1$。
• 将第 $4$ 行第 $2$ 列减去 $1$，在第 $2$ 行第 $5$ 列加上 $1$。
• 将第 $4$ 行第 $4$ 列减去 $1$，在第 $3$ 行第 $5$ 列加上 $1$。

【数据规模与约定】

对于全部的测试点，保证：

• $1 \leq n \leq 100$，$1 \leq m \leq n^2$。
• $1 \leq x, y \leq n$。
• 输入数据一定存在解。

【说明】

题目译自 COCI2008-2009 CONTEST #6 T3 NERED，翻译来自 @一扶苏一。