Forest

Mr. Jan owns a large forest that covers a square plot with side length $n$. The trees are planted on a grid, with $n$ trees in every row and $n$ trees in every column, for a total of $n^2$ trees. Each tree has a fixed age.

Mr. Jan wants to build a house of area $d$. To do that he must clear part of the forest, and since each tree occupies exactly $1$ unit of area, he must cut down exactly $d$ trees. The cleared trees have to form a single connected region, where two trees are adjacent only when they share an edge (up, down, left, or right); touching only at a corner does not count as connected.

Mr. Jan wants the oldest tree among all the ones he cuts down to be as young as possible. Find that minimum possible value.

The first line contains two integers $n$ and $d$ separated by a space ($1 \le n \le 1\,000$, $1 \le d \le n^2$): the side length of the forest and the area of the house Mr. Jan wants to build.

Each of the next $n$ lines contains $n$ integers $w(i, k)$ ($1 \le w(i, k) \le 10^9$), the age of the tree in the $i$-th row from the top and the $k$-th column from the left.

Print a single integer: over every valid connected region of exactly $d$ trees, the smallest possible age of the oldest tree in the region that is cut down.