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 \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 翻译