Score : $500$ points

问题描述

我们有一个具有 $H$ 行（水平）和 $W$ 列（垂直）的网格。令 $(i, j)$ 表示从上到下第 $i$ 行、从左到右第 $j$ 列的方格，其中 $(i, j)$ 包含一个整数 $A_{i,j}$。

高桥将从起点 $(1, 1)$ 出发，并重复向右或向下移动一格，直到到达终点 $(H, W)$。在此过程中，不允许离开网格。

这次旅行的成本定义为：

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

请找出最小可能的成本。

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 09:57:31