001 - 反転 (Flip)

時間制限 1 秒 / メモリ制限 256 MB / 得点 100 / x 1 /

TLE
1sec
MLE
256MB
得点
100

問題

H行W列のマス目に、それぞれ0または1が書き込まれています。 i行目のj列目にかかれている数はPi,jです。

JOIくんはこれから、以下の操作を行います。 まず、1 < A ≦ B < Hを満たす整数A,Bを選んで、A行目からB行目までのすべてのマスの値を反転します。 反転すると、0が書かれていたマスは1に、1が書かれていたマスは0になります。 次に、1 < C ≦ D < Wを満たす整数C,Dを選んで、C列目からD列目までのすべてのマスの値を反転します。

JOIくんは、整数A ,B ,C ,Dをうまく選ぶことによって、最終的に1が書かれているマスの個数を最小化したいです。 そのため、あなたは、最終的に1が書かれているマスの個数の最小値を求めるプログラムを作ることになりました。

入力

H W
P1,1 P1,2 ... P1,W
P2,1 P2,2 ... P2,W
:
PH,1 PH,2 ... PH,W

最初の1行には空白区切りで整数H,Wが与えられる。

続くH行にはマス目の最初の状態が与えられる。

i行目には、空白区切りでPi,1 ,Pi,2...Pi,Wが与えられる。

出力

最終的に1が書かれているマスの個数の最小値を1行に出力してください。

制約

全ての入出力ケースについて以下を満たす。

  • 3 ≦ H ,W ≦ 300
  • Pi,j=0 ,1

小課題

小課題1[10点]

以下の条件を満たす。

  • 3 ≦ H ,W ≦ 80

小課題2[90点]

追加の制約はない。

入出力例

入力例1

4 5
0 1 1 0 1
1 0 0 0 1
1 1 0 1 0
0 1 0 0 1

出力例1

6

解説

この例ではA=2 ,B=3 ,C=2 ,D=3と選んだ時が最小となる。

入力例2

7 6
0 1 0 0 1 1
0 0 0 0 1 0
1 1 1 1 1 0
1 1 0 1 0 1
1 0 0 1 1 0
0 1 0 0 1 1
1 1 0 0 1 1

出力例2

12