寻宝

题目描述

我们有一个 $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 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

数据范围

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