Score : $500$ points
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.
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}$
Print the answer.
1 3 2 3 4 5
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)$.
2 2 1 3 2 4 3
3
The minimum cost is achieved by traversing $(1,1)$, $(1,2)$, $(2,2)$ in this order.
3 5 3 4 7 8 6 4 6 7 3 10 2 3 8 1 10 4
21