Problem Description

Takahashi was abducted by a mysterious person X and confined in a mysterious facility. The floor of this facility has a grid of $ R $ rows and $ C $ columns, with each cell containing a single number. Takahashi is currently on the cell at the 1st row and 1st column.

After being confined for a long time, Takahashi is getting hungry. According to the mysterious person X, after exactly $ D $ moves of "moving to an adjacent cell," he will prepare a takoyaki (octopus dumpling) of the same price as the number written on the cell where Takahashi will be. An "adjacent cell" refers to a cell that shares an edge with the current cell. Takahashi wants to eat the most expensive takoyaki possible, so he decided to consider the maximum price of takoyaki he can eat.

Input Format

The input is given from the standard input in the following format:

$ 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} $

• The first line contains three integers representing the number of rows $R\ (2\ ≦\ R\ ≦\ 1,000)$, the number of columns $C\ (2\ ≦\ C\ ≦\ 1,000)$, and the number of moves Takahashi must make $D\ (1\ ≦\ D\ ≦\ 2,000)$, separated by spaces.
• The following $ R $ lines contain information about the numbers written on the grid. The $ i $-th line contains $ C $ integers separated by spaces. The $ j $-th integer $A_{i,j}\ (1\ ≦\ A_{i,j}\ ≦\ 999)$ represents the number written on the cell at the $ i $-th row and $ j $-th column.

Output Format

Output the maximum price of takoyaki that Takahashi can eat in one line. End the output with a newline.

Sample Input and Output

Sample Input #1

3 2 1
9 5
3 1
8 9

Sample Output #1

5

Sample Input #2

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

Sample Output #2

999

Sample Input #3

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

Sample Output #3

198

Notes/Hints

Partial Points

This problem has partial points.

• If you correctly solve all test cases where $R\ ≦\ 100$ and $C\ ≦\ 100$ and $D\ ≦\ 200$, you will be awarded $ 60 $ points.

Sample Explanation 1

After exactly 1 move, the only cells Takahashi can reach are the cell at the 1st row and 2nd column or the cell at the 2nd row and 1st column. In this case, Takahashi can eat a takoyaki with a maximum price of $ 5 $.

Sample Explanation 2

In this case, no matter how Takahashi moves, he can always eat a takoyaki with a price of $ 999 $.

Sample Explanation 3

In this case, no matter how Takahashi moves, he can only eat a takoyaki with a price of $ 198 $.

见题面 Input 部分

见题面 Output 部分