AT_ttpc2015_e マス目色ぬり

[problemUrl]: https://atcoder.jp/contests/ttpc2015/tasks/ttpc2015_e $ 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 $ を満たす。

赤色のマスの数と青色のマスの数の差の絶対値の最大値を出力せよ。出力は標準出力に行い、末尾に改行を入れること。

### Sample Explanation 1 この場合、$ (1,\ 1) $ と $ (1,\ 2) $ を選んだ場合に答えは最大になり、$ 2 $ になります。 他にも、$ (1,\ 1) $ と $ (2,\ 1) $ を選んだ場合や $ (1,1),(1,2),(2,1),(2,2) $ を選んだ場合も答えは $ 2 $ になります。 ### Sample Explanation 2 この場合、すべてのマス目が赤色に塗られます。なのですべてのマスを選ぶときが最大で答えは $ 9 $ です。 ### Sample Explanation 3 この場合、真ん中のマス目以外が青色に塗られます。なのでこの場合もすべてのマスを選ぶときが最大で答えは $ 7 $ です。