题目描述

小明今天遇到一个数学题：有 n 行总共 n*(n+1)/2 个数叠成了一个数塔，从上往下数第 i 行里面恰好有 i 个数。给定 k，你需要从中拿走恰好 k 个数，使得拿走的数的最小值最小。

一个数能被拿走当且仅当它左上角和右上角都没有数或者那个数已经被拿走了。

小明现在求助于你，请你帮他编程实现。

输入格式

第一行两个正整数 n 和 k 。

接下来 n 行，第 i 行有 i 个正整数 $a_{i1}$ , $a_{i2}$ , ......, $a_{ii}$ ，其中 $a_{ij}$ 表示从上往下第 i 行从左往右第 j 个数。

数据范围

1 <= n <= 2*$10^3$

1 <= k <= n*(n+1)/2

1 <= $a_{ij}$ <= 2019

输出格式

一个整数，即拿走的数的最小值的最小值。

样例

5 7
1999
2019 2010
850 1500 1600
900 900 710 900
1000 800 600 800 1000

710

样例解释

左边为数塔，右边为最优拿数顺序。