問題文
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 。