当前没有测试数据。

F - 藏宝

得分：$500$ 分

题目描述

我们有一个 $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 3 2
3 4 5

9

只有一种行进方式，所经过的方格上的整数从大到小分别为 $5$、$4$、$3$，因此输出 $9(=5+4)$。

2 2 1
3 2
4 3

3

按照 $(1,1)$、$(1,2)$、$(2,2)$ 的顺序行进可以得到最小费用。

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

21

按照 $(3, 1)$、$(2, 1)$、$(3, 5)$、$(2, 5)$、$(1, 5)$、$(1, 4)$、$(2, 4)$ 的顺序行进可以得到最小费用。