No.861 ケーキカット

レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 26
作問者 : nmnmnmnmnmnmnmnmnmnmnmnmnmnm / テスター : testestesttestestest
3 ProblemId : 2254 / 出題時の順位表

問題文

5行5列のサイズの正方形のケーキがありA君とB君の2人で分けます。

ケーキの$i$行目$j$列目には美味しさ$C_{ij}$が決められています。
$i$行目$j$列目のケーキはA君かB君かいずれかのものになります。

さて、ケーキをカットしてから2人に分けることにします。
カットは行と行の間、列と列の間でカットできますが、ここで条件があります。

A君、B君に行き渡るそれぞれのケーキの部分は2つに切り分け、それぞれ連結でなければいけません。
(連結とはあるi行j列目のケーキ部分に辺で接する隣り合うケーキ部分が切り離されないことをいう。)

A君とB君にケーキが残らずに行き渡った時、それぞれの美味しさの合計の差を最小にしたいです。
最小になるように切ったとき、その差を(負でない整数で)求めよ。

入力

$C_{00}$ $C_{01}$ $C_{02}$ $C_{03}$ $C_{04}$
$C_{10}$ $C_{11}$ $C_{12}$ $C_{13}$ $C_{14}$
$C_{20}$ $C_{21}$ $C_{22}$ $C_{23}$ $C_{24}$
$C_{30}$ $C_{31}$ $C_{32}$ $C_{33}$ $C_{34}$
$C_{40}$ $C_{41}$ $C_{42}$ $C_{43}$ $C_{44}$

$C_{ij}$は$i$行$j$列目のケーキの美味しさ。
$C_{ij}$は正の整数。$1 \le C_{ij} \le 1000000000=10^9$

出力

答えを1行で出力せよ。
最後に改行してください。

サンプル

サンプル1
入力
3 5 4 1 6
6 3 4 3 1 
3 2 4 7 6
4 5 6 2 1
1 4 3 5 2
出力
1

例えば下のような切り方があります。(赤い線が切るところです。)
2つに分けられたケーキはいずれも連結しています。

サンプル2
入力
8 2 4 3 1
3 3 8 7 2
1 3 6 6 2
4 5 9 2 5
2 3 3 4 2
出力
0

下のようなドーナツ状の切り方もできます。

サンプル3
入力
200 3 2 1 5
5 15 4 5 6
7 6 5 1 7
3 10 2 3 11
2 4 1 6 10
出力
76

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。