seuOJ320 - 取数游戏

有 $\frac {n(n+1)} {2}$ 个数排成高度为 $n$ 的三角形，从上往下数第 $i$ 行恰好有 $i$ 个数。下面是一个 $10$ 个数排成高度为 $4$ 的三角形的示例：

     1   
   2   3 
 4   5   6
7  8   9  10

我们用 $a_{i,j} (j \le i \le n)$ 来表示第 $i$ 行第 $j$ 列的数，例如在上面的例子中， $a_{3,2}=5$ 。

取数的过程是从上往下进行的，因此一个数可以被取走，当且仅当它的左上角和右上角的位置都没有数，或者有数已经被取走。

例如在上面的例子中，要想取走 $5$ ，必须先取走 $2$ 和 $3$ ；要想取走 $3$ ，必须先取走 $1$ ；而 $1$ 可以直接取走，不必在此之前先取走任何其它数。

现在给定一个 $k$ ，你需要从三角形中取走至多 $k$ 个数，使得取走的所有数中的最小值尽可能小，你需要输出这个最小值。

第一行共两个正整数 $n (1 \le n \le 500)$ 和 $k (1 \le k \le \frac {n(n+1)} 2)$ 。

接下来 $n$ 行，第 $i$ 行有 $i$ 个正整数，分别表示 $a_{i,1},a_{i,2},...,a_{i,i} (1 \le a_{i,j} \le 3000)$ 。

输出一行一个整数，表示取走的数中的最小值的最小值。