题目描述

有一个正三角形的数塔，数塔有n 行，总共n(n+1)/2个数，数塔 的第i 行恰好有i个数。 现在给定一个整数 k，让你从数塔中拿走恰好k 个数，要求是拿走的k个数的最小值最小。 当然，不是随意从数塔中拿数，拿走的每一个数的前提是这个数的左上方和右上方都没有数（或者左上方和 右上方的数已经被拿走了）。

输入格式

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

接下来 n行，第 i 行有i个正整数a​[i,1]​,a[i,2]​,…,a​[i,j]​,其中a[i,j]表示从上往下第i 行从左往右第j个数。

输出格式

输出一行一个整数，即拿走的那些数的最小值。

样例

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

710

样例​1​说明

左边为数塔，右边为其中一种最优的拿数顺序。

数据范围

1 ≤ n ≤ 2 x 1000

1 ≤ k ≤ n(n+1)/2

1 ≤ a[i,j] ≤ 2019