B - 謎の人物X Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋君は謎の人物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} であることを表す。

部分点

この問題には部分点が設定されている。

  • R ≦ 100 かつ C ≦ 100 かつ D ≦ 200 を満たすテストケースすべてに正解した場合は 60 点が与えられる。

出力

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

入力例1

3 2 1
9 5
3 1
8 9

出力例1

5

ちょうど 1 回移動することで行くことが出来るマスは、1 行目の 2 列目のマスか 2 行目の 1 列目のマスだけです。このケースでは、高橋君は最大で 5 円のたこ焼きを食べることが出来ます。

入力例2

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

出力例2

999

このケースでは、高橋君はどのように移動しても 999 円のたこ焼きを食べることが出来ます。

入力例3

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

出力例3

198

このケースでは、高橋君はどのように移動しても 198 円のたこ焼きしか食べることが出来ません。