E - マス目色ぬり Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

N × N のマス目が与えられます。 上から i(1 \leq i \leq N) 番目、左から j(1 \leq j \leq N) 番目のマスを (i,\ j) とします。

マスそれぞれを、i+j が偶数ならば赤色、奇数ならば青色に塗ります。

次に、K 個のマスについて、そのマスが赤色に塗られていたら青色、青色に塗られていたら赤色に塗り直します。

その後、あなたはいくつかのマスを選びます。ただし、選んだマスたちは1つの穴のない長方形とならなければいけません。

そして、選んだマスたちのうち赤色のマスの数と青色のマスの数の差の絶対値ができる限り大きくなるようにしたいです。最大でいくつになるでしょうか。

入力

入力は以下の形式で標準入力から与えられる。

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 です。