I. Ivan and the swimming pool
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

After another great year for UFPE's competitive programming team, the coach Ivan decided to gift the team and invest in building a pool at an area nearby. After reuniting with the group to arrange the details, four things were decided:

  • The pool must have size S.
  • It cannot have separate parts.
  • All areas of the pool must be equally deep.
  • It has to be as deep as possible.

There was only one limitation stopping us from always digging deeper: Rocks. Because of rocks underground, it wouldn't be possible to dig more than a certain depth in each part of the area.

To help us pick the best place for the pool, we split the area in cells, measured how deep we could dig in each of them and mapped it into a grid, such as the one shown below:

$$$$$$ \begin{array}{|c|c|c|c|} \hline 9 & 7 & 7 & 9 \\ \hline 7 & 8 & 8 & 7 \\ \hline \end{array} $$$$$$

To help us estimate the costs of the building, you must calculate the maximum possible depth of the pool.

Input

S, N and M, the size of the pool and the dimensions of the terrain. Followed by N lines with M integers on each, the depth of each cell on the area.

$$$1 \le N$$$, $$$M \le 10^{6}$$$, $$$S \le N \cdot M \le 10^{6}$$$, $$$1 \le$$$ Depths $$$\le 10^{8}$$$

Output

D, the maximum depth of the pool.

Examples
Input
1 2 4
9 7 7 9
7 8 8 7
Output
9
Input
2 2 4
9 7 7 9
7 8 8 7
Output
8
Input
3 2 4
9 7 7 9
7 8 8 7
Output
7
Note

In the case presented on the statement, for a pool of size 1, we could choose one of the 9 units deep cells to have a 9 units deep pool.

For a pool of size 2 however, the deepest it could be is 8 units, by choosing both cells with 8 units deep. Because the 9 units deep cells aren't connected and combining one of them with a 7 units deep cell would make the entire pool 7 units deep.

For all other sizes, you must use at least one 7 deep cell to keep the pool connected, so the pool would be 7 units deep.