分数: 500 点
问题陈述
我们有一个网格 H 水平行和 W 垂直列。让 (i, j) 表示 i从顶部开始的第行和 j左起第 列。 (i, j) 包含一个整数 A_{i,j}.
高桥将出发 (1, 1) 并重复向右或向下移动一格,直到到达 (H, W)。不允许退出网格。
这次旅行的费用定义为:
的总和 K 上写的整数中最大的整数 已遍历 H+W-1 方格。
找出可能的最小成本。
约束
- 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