ある N 人の兄弟は親の遺産相続の話し合いをしていた. 彼らの親の残した莫大な遺産の中には広大な土地も含まれていた. その土地は南北に H km, 東西に W km に広がる長方形の形をしている. この土地は 1 km 四方の区画単位で管理されており, 土地の北端から i 〜 i+1 km かつ西端から j 〜 j+1 km の範囲にある 1 km 四方の区画を区画 (i,j) と呼ぶ. (i, j は 0≤i<H, 0≤j<W を満たす整数である.) 土地の価格は区画ごとに決まっており,区画 (i,j) の価格は ai,j で表される.
兄弟は次のように土地を分けて相続することにした.
ある人が相続する土地の範囲に含まれる区画の価格の和をその土地の価格と呼ぶ. 兄弟は,各々が相続する土地の価格がなるべく公平になるように土地を分けたい. あなたの仕事は, N 人の中で相続する土地の価格が 最も低い人の土地の価格を最大にするような土地の分け方を考えることである. そのように土地を分けた時の,相続する土地の価格が最も低い人の土地の価格を答えるプログラムを作成せよ.
入力は以下のような形式で与えられる.
H W N
a0,0 a0,1 ... a0,W−1
...
aH−1,0 aH−1,1 ... aH−1,W−1
H, W (2≤H,W≤200) は遺産の土地の南北の長さと東西の長さをそれぞれ表す. N (2≤N≤4) は土地を相続する兄弟の人数を表す. ai,j (0≤ai,j≤104) は区画 (i,j) の価格を表す.
相続する土地の価格が最も低い人の土地の価格を最大にするように分けた時の, 最も低い土地の価格を 1 行で出力せよ.
3 3 2 1 2 2 3 1 0 0 4 3
7
図のように分けるのが最適である.
3 3 2 0 1 0 1 1 1 0 1 0
1
2 5 3 8 3 0 5 6 2 5 2 5 2
11
3 3 4 3 3 4 3 3 4 3 3 4
7
4 4 4 2 2 2 2 2 1 2 1 2 2 2 2 2 1 2 1
7