Maximize the Minimum in the Number Tower Removal

Consider a number tower with \(n\) rows containing a total of \(\frac{n(n+1)}{2}\) numbers. The numbers are arranged in a triangular form: the first row has 1 number, the second row has 2 numbers, and so on.

You are allowed to remove exactly \(k\) numbers from the tower subject to the following rule: A number can be removed if and only if its upper‐left neighbor and upper–right neighbor (if they exist) have already been removed (or do not exist). For the leftmost numbers (i.e. when the upper–left neighbor does not exist) the condition holds automatically, and similarly for the rightmost numbers.

Define the value \(X\) of a removal set as the minimum number among all the removed numbers. Your task is to choose a valid removal set of exactly \(k\) numbers so that \(X\) is maximized.

Notes

• If a number (except those on the boundary) is removed then both of its two adjacent numbers in the row above must also be removed.
• The removal set is said to be valid if it satisfies the dependency condition described above.

inputFormat

The first line contains two integers \(n\) and \(k\) \((1 \le n \le 10^3,\; 1 \le k \le \frac{n(n+1)}{2})\) separated by a space.

Then follow \(n\) lines. The \(i\)-th line contains \(i\) integers representing the numbers in the \(i\)-th row of the tower. All numbers are between \(1\) and \(10^9\) (inclusive).

outputFormat

Output a single integer: the maximum possible value of the minimum number among the \(k\) removed numbers if the removals are performed in a valid order.

sample

3 3
5
4 6
8 9 7

5