[ARC023B] 謎の人物X

题意翻译

题目大意: 给出一个R行C列的矩阵,从第一行第一列出发,走了D步之后可以到达的数的最大值是多少? (规定不能斜向走,向前后左右四个方向移动一次算一步) 输入: 一行,三个整数 R,C,D,2 ≤ R,C ≤ 1000,1 ≤ D ≤ 2000。 接下来R行,每行C个正整数,是对矩阵的描述,矩阵中每个数小于999。 输出: 一行,一个整数,即可以到达的数的最大值。

题目描述

[problemUrl]: https://atcoder.jp/contests/arc023/tasks/arc023_2 高橋君は謎の人物Xに連れ去られてしまい、謎の施設に閉じ込められてしまいました。この施設の床には $ R $ 行 $ C $ 列 のマス目が書かれていて、それぞれのマスには $ 1 $ つずつ数字が書かれています。高橋君はこのマス目の $ 1 $ 行目の $ 1 $ 列目のマスにいます。 長い時間閉じ込められていたので、高橋君はお腹が減ってきました。謎の人物Xによると、「隣のマスに移動する」ということをちょうど $ D $ 回行った後に高橋君がいるマスに書いてある数字と同じ値段のたこ焼きを用意してくれるそうです。あるマスの「隣のマス」とは、そのマスと辺を共有するマスのことを指します。高橋君は出来るだけ値段の高いたこ焼きが食べたいと思ったので、最大でいくらのたこ焼きを食べることが出来るかを考えることにしました。

输入输出格式

输入格式


入力は以下の形式で標準入力から与えられる。 > $ R $ $ C $ $ D $ $ A_{1,1} $ $ A_{1,2} $ ... $ A_{1,C} $ $ A_{2,1} $ $ A_{2,2} $ ... $ A_{2,C} $ : $ A_{R,1} $ $ A_{R,2} $ ... $ A_{R,C} $ - $ 1 $ 行目には、マス目の行数を表した整数 $ R\ (2\ ≦\ R\ ≦\ 1,000) $ と、マス目の列数を表した整数 $ C\ (2\ ≦\ C\ ≦\ 1,000) $ と、高橋君が移動しなければならない回数を表した整数 $ D\ (1\ ≦\ D\ ≦\ 2,000) $ が空白区切りで与えられる。 - 続く $ R $ 行には、マス目に書かれている数字の情報が与えられる。このうちの $ i $ 番目の行には $ C $ 個の整数が空白区切りで与えられる。このうち $ j $ 番目の整数 $ A_{i,j}\ (1\ ≦\ A_{i,j}\ ≦\ 999) $ は、$ i $ 行目の $ j $ 列目のマスに書かれている数字が $ A_{i,j} $ であることを表す。

输出格式


高橋君が食べることができるたこ焼きの値段の最大値を $ 1 $ 行に出力せよ。出力の末尾に改行をいれること。

输入输出样例

输入样例 #1

3 2 1
9 5
3 1
8 9

输出样例 #1

5

输入样例 #2

4 4 100
999 999 999 999
999 999 999 999
999 999 999 999
999 999 999 999

输出样例 #2

999

输入样例 #3

3 4 5
700 198 700 198
198 700 198 700
700 198 700 198

输出样例 #3

198

说明

### 部分点 この問題には部分点が設定されている。 - $ R\ ≦\ 100 $ かつ $ C\ ≦\ 100 $ かつ $ D\ ≦\ 200 $ を満たすテストケースすべてに正解した場合は $ 60 $ 点が与えられる。 ### Sample Explanation 1 ちょうど $ 1 $ 回移動することで行くことが出来るマスは、$ 1 $ 行目の $ 2 $ 列目のマスか $ 2 $ 行目の $ 1 $ 列目のマスだけです。このケースでは、高橋君は最大で $ 5 $ 円のたこ焼きを食べることが出来ます。 ### Sample Explanation 2 このケースでは、高橋君はどのように移動しても $ 999 $ 円のたこ焼きを食べることが出来ます。 ### Sample Explanation 3 このケースでは、高橋君はどのように移動しても $ 198 $ 円のたこ焼きしか食べることが出来ません。