AT_abc358_g [ABC358G] AtCoder Tour

[problemUrl]: https://atcoder.jp/contests/abc358/tasks/abc358_g AtCoder Land は $ H $ 行 $ W $ 列のグリッドで表されます。上から $ i $ 番目、左から $ j $ 番目のマスを $ (i,\ j) $ と表記します。 高橋君ははじめマス $ (S_i,\ S_j) $ におり、以下の行動を $ K $ 回繰り返します。 - 高橋君は現在いるマスに留まるか、隣のマスに移動する。その後の時点で高橋君がいるマスを $ (i,\ j) $ として $ A_{i,\ j} $ の楽しさを得る。 高橋君が得ることのできる楽しさの合計の最大値を求めてください。 ただし、マス $ (x',\ y') $ がマス $ (x,\ y) $ の隣のマスであるとは $ |x\ -\ x'|\ +\ |y\ -\ y'|\ =\ 1 $ であることを指します。

入力は以下の形式で標準入力から与えられる。 > $ H $ $ W $ $ K $ $ S_i $ $ S_j $ $ 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\ 50 $ - $ 1\ \leq\ K\ \leq\ 10^9 $ - $ 1\ \leq\ S_i\ \leq\ H $ - $ 1\ \leq\ S_j\ \leq\ W $ - $ 1\ \leq\ A_{i,\ j}\ \leq\ 10^9 $ - 入力される値はすべて整数 ### Sample Explanation 1 高橋君は以下のように行動することで楽しさの合計を $ 14 $ にすることができます。 - はじめ、高橋君は $ (1,\ 2) $ にいる。 - 高橋君はマス $ (2,\ 2) $ に移動する。その後、$ A_{2,\ 2}\ =\ 4 $ の楽しさを得る。 - 高橋君はマス $ (2,\ 3) $ に移動する。その後、$ A_{2,\ 3}\ =\ 5 $ の楽しさを得る。 - 高橋君はマス $ (2,\ 3) $ に留まる。その後、$ A_{2,\ 3}\ =\ 5 $ の楽しさを得る。 高橋君は楽しさの合計を $ 14 $ より大きくすることはできないため、$ 14 $ を出力します。