AT_abc227_f [ABC227F] Treasure Hunting

题目描述

有一个纵向 $H$ 行、横向 $W$ 列的网格。我们将从上到下第 $i$ 行、从左到右第 $j$ 列的格子记作 $(i,j)$。在 $(i,j)$ 格子上写有整数 $A_{i,j}$。

高桥君从 $(1,1)$ 出发，每次可以向右或向下移动一格，直到到达 $(H,W)$。在移动过程中，不能走出网格。

此时，移动的代价定义如下：

经过的 $H+W-1$ 个格子中，所写整数中较大的 $K$ 个数的和。

请你求出可能的最小代价。

输入格式

输入以如下格式从标准输入给出。

$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

1 3 2
3 4 5

输出 #1

9

输入输出样例 #2

输入 #2

2 2 1
3 2
4 3

输出 #2

3

输入输出样例 #3

输入 #3

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

输出 #3

21

说明/提示

限制条件

• $1 \leq H, W \leq 30$
• $1 \leq K < H+W$
• $1 \leq A_{i,j} \leq 10^9$
• 所有输入均为整数

样例解释 1

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

样例解释 2

依次经过 $(1,1)$、$(1,2)$、$(2,2)$ 时，代价最小。

由 ChatGPT 4.1 翻译