← 返回题目列表

AtCoder · abc227_f

I. 寻宝

中文机器翻译题面 查看原题

分数: 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