问题陈述

有N个兄弟在讨论父母的遗产继承问题。在他们父母留下的巨大遗产中，包括了广阔的土地。这片土地呈长方形，南北宽度为H公里，东西长度为W公里。该土地以1平方公里的单位进行管理，从土地的北端到西端的距离为i到i+1公里，从土地的西端到东端的距离为j到j+1公里的区域被称为(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```

### 示例输出1

```plain
7```

最佳划分如下图：

![](/img/other/jag2016_domestic/fig/f-figure.png)

---

### 示例输入2

```plain
3 3 2
0 1 0
1 1 1
0 1 0```

### 示例输出2

```plain
1```

---

### 示例输入3

```plain
2 5 3
8 3 0 5 6
2 5 2 5 2```

### 示例输出3

```plain
11```

---

### 示例输入4

```plain
3 3 4
3 3 4
3 3 4
3 3 4```

### 示例输出4

```plain
7```

---

### 示例输入5

```plain
4 4 4
2 2 2 2
2 1 2 1
2 2 2 2
2 1 2 1```

### 示例输出5

```plain
7```