0889 - 幹線道路 (Trunk Road)

問題

JOI 市は，東西方向にまっすぐに伸びる H 本の道路と，南北方向にまっすぐに伸びる W 本の道路によって，碁盤の目の形に区分けされている．道路と道路の間隔は 1 である．JOI 市では，これら H+W 本の道路から，東西方向に 1 本，南北方向に 1 本，合計 2 本の道路を幹線道路として選ぶことになった．

北から i 本目 (1 ≦ i ≦ H) の道路と，西から j 本目 (1 ≦ j ≦ W) の道路の交差点を，交差点 ( i , j ) とする．交差点 ( i , j ) と北から m 本目 (1 ≦ m ≦ H) の道路の距離は |i−m| であり，交差点 ( i , j ) と西から n 本目 (1 ≦ n ≦ W) の道路の距離は |j−n| である． また，交差点 ( i , j ) の近くには A_i,j 人の住人が住んでいる．

2 本の幹線道路を選んだときの，JOI 市の全ての住人に対する，最寄りの交差点から近い方の幹線道路への距離の総和の最小値を求めよ．

制約

• 2 ≦ H ≦ 25
• 2 ≦ W ≦ 25
• 0 ≦ A_i,j ≦ 100 (1 ≦ i ≦ H,1 ≦ j ≦ W)

入力

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

H W
A1,1 A1,2 ... A1,W
:
AH,1 AH,2 ... AH,W

出力

JOI 市の全ての住人に対する，最寄りの交差点から近い方の幹線道路への距離の総和の最小値を出力せよ．

小課題

小課題 1 [10点]

• A_i,j = 1 (1 ≦ i ≦ H, 1 ≦ j ≦ W)

小課題 2 [90点]

• 追加の制限はない．

入出力例

入力例 1

3 5
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1

出力例 1

8

例えば，北から 2 本目の道路と西から 1 本目の道路を幹線道路とすればよい．

---

入力例 2

5 5
1 2 3 1 5
1 22 11 44 3
1 33 41 53 2
4 92 35 23 1
4 2 6 3 5

出力例 2

164

北から 3 本目の道路と西から 2 本目の道路を幹線道路とすればよい．