{"problem":{"name":"Treasure Hunting","description":{"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}","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc227_f"},"statements":[{"statement_type":"Markdown","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.\n\n## Constraints\n\n*   $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.\n\n## Input\n\nInput 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}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc227_f","tags":[],"sample_group":[["1 3 2\n3 4 5","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)$."],["2 2 1\n3 2\n4 3","3\n\nThe minimum cost is achieved by traversing $(1,1)$, $(1,2)$, $(2,2)$ in this order."],["3 5 3\n4 7 8 6 4\n6 7 3 10 2\n3 8 1 10 4","21"]],"created_at":"2026-03-03 11:01:14"}}