Mining

A mine of $N$ rows and $M$ columns rests on the ground. It is made of $N \times M$ minerals of size $1 \times 1$, and the mineral in row $i$, column $j$ has strength $S_{i,j}$.

The top face of the mine, its left face and its right face touch air. Its bottom face rests on the ground.

You want to mine these minerals with a mining machine. The mining machine can pick any mineral that has at least one face touching air and mine it. A mineral whose four faces all touch the ground or other minerals cannot be mined. Once a mineral is mined, air fills the square it occupied, so minerals further inside become exposed.

A machine of performance $D$ can mine only the minerals whose strength is at most $D$. Find the smallest $D$ that lets the machine mine at least $K$ minerals.

The first line contains $N$, $M$ and $K$. ($1 \le N, M \le 1000$, $1 \le K \le N \times M$)

Each of the next $N$ lines gives the strengths of one row of minerals, from the top row down. Line $i$ contains $M$ integers $S_{i,1}, S_{i,2}, \dots, S_{i,M}$ separated by spaces. ($1 \le S_{i,j} \le 10^6$)

Print the smallest performance $D$ that lets the machine mine at least $K$ minerals.