题目描述

我们有一个 $H$ 行 $W$ 列的网格。用 $(i, j)$ 表示从上到下数第 $i$ 行、从左到右数第 $j$ 列的方块，$(i, j)$ 包含一个整数 $A_{i,j}$。

高桥将从 $(1, 1)$ 出发，每次向右或向下移动一个方块，直到到达 $(H, W)$。不允许离开网格。

此次旅行的花费定义为：

经过的 $H+W-1$ 个方块中，最大的 $K$ 个整数之和。

找出可能的最小花费。

约束条件

• $1 \\leq H,W \\leq 30$
• $1 \\leq K < H+W$
• $1 \\leq A_{i,j} \\leq 10^9$
• 输入中的所有值都是整数。

输入

输入以以下格式从标准输入给出：

$H$ $W$ $K$ $A_{1,1}$ $A_{1,2}$ $\\ldots$ $A_{1,W}$ $A_{2,1}$ $A_{2,2}$ $\\ldots$ $A_{2,W}$ $\\vdots$ $A_{H,1}$ $A_{H,2}$ $\\ldots$ $A_{H,W}$

输出

输出答案。

示例输入 1

1 3 2
3 4 5

示例输出 1

9

只有一种旅行方式，经过的方块包含从大到小的整数 $5$、$4$、$3$，因此输出 $9(=5+4)$。

示例输入 2

2 2 1
3 2
4 3

示例输出 2

3

按照这个顺序遍历 $(1,1)$、$(1,2)$、$(2,2)$ 可以得到最小花费。

示例输入 3

3 5 3
4 7 8 6 4
6 7 3 10 2
3 8 1 10 4

示例输出 3

21