{"raw_statement":[{"iden":"problem statement","content":"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}$.\nTakahashi will depart $(1, 1)$ and repeatedly move one square right or down until reaching $(H, W)$. It is not allowed to exit the grid.\nThe cost of this travel is defined as:\n\n> the sum of the $K$ greatest integers among the integers written on the $H+W-1$ squares traversed.\n\nFind the minimum possible cost."},{"iden":"constraints","content":"*   $1 \\leq H,W \\leq 30$\n*   $1 \\leq K < H+W$\n*   $1 \\leq A_{i,j} \\leq 10^9$\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$H$ $W$ $K$\n$A_{1,1}$ $A_{1,2}$ $\\ldots$ $A_{1,W}$\n$A_{2,1}$ $A_{2,2}$ $\\ldots$ $A_{2,W}$\n$\\vdots$\n$A_{H,1}$ $A_{H,2}$ $\\ldots$ $A_{H,W}$"},{"iden":"sample input 1","content":"1 3 2\n3 4 5"},{"iden":"sample output 1","content":"9\n\nThere 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)$."},{"iden":"sample input 2","content":"2 2 1\n3 2\n4 3"},{"iden":"sample output 2","content":"3\n\nThe minimum cost is achieved by traversing $(1,1)$, $(1,2)$, $(2,2)$ in this order."},{"iden":"sample input 3","content":"3 5 3\n4 7 8 6 4\n6 7 3 10 2\n3 8 1 10 4"},{"iden":"sample output 3","content":"21"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}