/ 
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
縦 H 行、横 W 列のマス目があります。上から i 行目、左から j 列目のマスを (i,j) と書くことにします。(i,j) には整数 A_{i,j} が書かれています。
高橋君は (1,1) を出発し、(H,W) にたどり着くまで、1 つ右あるいは 1 つ下のマスへ移動することを繰り返します。ただし、マス目の外に出ることはできません。
この時、移動のコストを以下のように定義します。
通った 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
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}
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