102275: [AtCoder]ABC227 F - Treasure Hunting

Problem Statement

We have a grid with $H$ horizontal rows and $W$ vertical columns. Let $(i, j)$ denote the square at the $i$-th row from the top and $j$-th column from the left. $(i, j)$ contains an integer $A_{i,j}$.

Takahashi will depart $(1, 1)$ and repeatedly move one square right or down until reaching $(H, W)$. It is not allowed to exit the grid.

The cost of this travel is defined as:

the sum of the $K$ greatest integers among the integers written on the $H+W-1$ squares traversed.

Find the minimum possible cost.

Constraints

• $1 \leq H,W \leq 30$
• $1 \leq K < H+W$
• $1 \leq A_{i,j} \leq 10^9$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$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}$

Output

Print the answer.

Sample Input 1

1 3 2
3 4 5

Sample Output 1

9

There is only one way to travel, where the traversed squares contain the integers $5$, $4$, $3$ from largest to smallest, so we print $9(=5+4)$.

Sample Input 2

2 2 1
3 2
4 3

Sample Output 2

3

The minimum cost is achieved by traversing $(1,1)$, $(1,2)$, $(2,2)$ in this order.

Sample Input 3

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

Sample Output 3

21

问题描述

我们有一个由$H$行和$W$列组成的网格。令$(i, j)$表示从顶部数第$i$行、从左数第$j$列的方格。$(i, j)$包含一个整数$A_{i,j}$。

高桥将从$(1, 1)$出发，反复向右或向下移动一个方格，直到到达$(H, W)$。不允许离开网格。

此次旅行的费用定义为：

在经过的$H+W-1$个方格中，$K$个最大的整数之和。

找到最小可能的费用。

限制条件

• $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