AT_abc227_f [ABC227F] Treasure Hunting

[problemUrl]: https://atcoder.jp/contests/abc227/tasks/abc227_f 縦 $ H $ 行、横 $ W $ 列のマス目があります。上から $ i $ 行目、左から $ j $ 列目のマスを $ (i,j) $ と書くことにします。$ (i,j) $ には整数 $ A_{i,j} $ が書かれています。 高橋君は $ (1,1) $ を出発し、$ (H,W) $ にたどり着くまで、$ 1 $ つ右あるいは $ 1 $ つ下のマスへ移動することを繰り返します。ただし、マス目の外に出ることはできません。 この時、移動のコストを以下のように定義します。 > 通った $ H+W-1 $ 個のマスに書かれた整数のうち大きい方 $ K $ 個の和 コストとしてありうる最小値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ 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\ \leq\ H,W\ \leq\ 30 $ - $ 1\ \leq\ K\