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