问题陈述
一个$N$的兄弟正在讨论继承父母遗产的事。 在父母留下的庞大遗产中,包括广阔的土地。 这片土地呈矩形,南北延伸$H$公里,东西向$W公里。 该土地以1平方公里为单位管理, 在北端$i$至$i+1$、西端$j$至$j+1$范围内的1公里见方地块称为$(i, j)$地块。 ($i$ 和 $j$ 是满足 $0 \leq i < H$ 和 $0 \leq j < W$ 的整数。) 土地价格为每个地块确定,地块$(i, j)$的价格表示为$a_{i, j}$。
兄弟们决定分割土地并继承如下。
- $N$ 每个兄弟选择几个地块继承。
- 各兄弟继承的土地必须选择成一个长方形。
- $N$ 个兄弟继承的土地不得重叠。
- 允许存在无人继承的地块。无人继承的地块将被放弃。
一个继承人的土地价格被定义为其土地范围内所有地块价格的总和。 兄弟们希望尽量公平地划分土地,使每个人继承的土地价格接近。 你的任务是,考虑如何划分土地,使 $N$ 个兄弟中继承土地价格最低的人所继承的土地价格达到最大。 请编写程序,计算按照这种方式划分土地时,继承土地价格最低的人所继承的土地价格。
输入
输入将以如下格式给出。
$H$$W$$N$
$a_{0,0}$ $a_{0,1}$ ... $a_{0,W-1}$
...
$a_{H-1,0}$ $a_{H-1,1}$ ... $a_{H-1,W-1}$
$H$ 和 $W$ $(2 \leq H, W \leq 200)$ 分别代表遗产土地的南北走向和东西走向长度。 $N$$(2 \leq N \leq 4)$ 代表兄弟继承土地的季节。 $a_{i, j}$ $(0 \leq a_{i,j} \leq 10^4)$ 表示地块 $(i, j)$ 的价格。
输出
当将继承权最低者的土地价格分割以最大化土地价格时, 用一条线输出最低的土地价格。
示例输入 1
3 3 2 1 2 2 3 1 0 0 4 3
样本输入 1 的输出
7
最好按照图示进行分割。
示例输入 2
3 3 2 0 1 0 1 1 1 0 1 0
样本输入 2 的输出
1
示例输入 3
2 5 3 8 3 0 5 6 2 5 2 5 2
样本输入 3 的输出
11
示例输入 4
3 3 4 3 3 4 3 3 4 3 3 4
样本输入 4 的输出
7
示例输入 5
4 4 4 2 2 2 2 2 1 2 1 2 2 2 2 2 1 2 1
样本输入 5 的输出
7