Contest Duration: - (local time) (100 minutes) Back to Home
F - Treasure Hunting /

Time Limit: 3 sec / Memory Limit: 1024 MB

### 問題文

H 行、横 W 列のマス目があります。上から i 行目、左から j 列目のマスを (i,j) と書くことにします。(i,j) には整数 A_{i,j} が書かれています。

この時、移動のコストを以下のように定義します。

コストとしてありうる最小値を求めてください。

### 制約

• 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


### 入力例 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


Score : 500 points

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


### 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