← 返回题目列表

AtCoder · ttpc2015_e

E. 方形着色

中文机器翻译题面 查看原题

問題文

N × N 会给出格子。 从上到下 i(1 \leq i \leq N) 左起第 th j(1 \leq j \leq N) 广场 我们将其表示为 (i,\ j) 。

每个格子,i+j 如果是偶数则涂成红色,如果是奇数则涂成蓝色。

接下来,K 对于若干格子,如果格子是红色的就涂成蓝色,如果格子是蓝色的就涂成红色。

之后,你选择一些格子。不过,选择的格子必须形成一个没有空洞的矩形。

然后,希望所选格子中红色格子与蓝色格子数量的差的绝对值尽可能大。最大可以是多少呢。


入力

输入是按以下格式从标准输入给出的。

N K
Y_1 X_1
Y_2 X_2
:
Y_K X_K
  • 1 行是一个整数 N(1 \leq N \leq 2000)、K(1 \leq K \leq 10) 用空格分隔。
  • 之后 K 行中给出了需要重新涂色的格子信息。在这些信息中 i 行是一个整数 Y_i(1 \leq Y_i \leq N)、X_i(1 \leq X_i \leq N) 以空格分隔,即 (Y_i,\ X_i) 表示重新涂该格子的颜色。
  • i \neq j 然后,Y_i \neq Y_j 或 至少 X_i \neq X_j 很满意。

出力

输出红色格子数与蓝色格子数差的绝对值的最大值。输出到标准输出,并在末尾加上换行。


入力例1

3 1
1 1

出力例1

2

在这种情况下, 创建一个(1, 1) 和 按字典顺序比较 (1, 2) 如果选择,会使答案最大,2 将会是。 其他还有,(1, 1) 和 按字典顺序比较 (2, 1) 如果选择,或者 (1,1),(1,2),(2,1),(2,2) 如果选择,答案也是 2 。


入力例2

3 4
1 2
2 1
2 3
3 2

出力例2

9

在这种情况下,所有格子都会被涂成红色。所以当选择所有格子时答案最大,为 9 。


入力例3

3 4
1 1
1 3
3 1
3 3

出力例3

7

在这种情况下,除了中间的格子以外的所有格子都会被涂成蓝色。所以在这种情况下选择所有格子时,答案也最大,为 7 。