题目背景

无

题目描述

在一个凹槽中放置了 n 层砖块、最上面的一层有n 块砖，从上到下每层依次减少一块砖。每块砖
都有一个分值，敲掉这块砖就能得到相应的分值，如下图所示。
14 15  4  3  23
 33  33 76  2
   2   13 11
     22 23
       31
如果你想敲掉第 i 层的第j 块砖的话，若i=1，你可以直接敲掉它；若i>1，则你必须先敲掉第
i-1 层的第j 和第j+1 块砖。
你现在可以敲掉最多 m 块砖，求得分最多能有多少。

输入格式：

输入文件的第一行为两个正整数 n 和m；接下来n 行，描述这n 层砖块上的分值a[i][j],满足
0≤a[i][j]≤100。
对于 100%的数据，满足1≤n≤50，1≤m≤n*(n+1)/2；

输出格式：

输出文件仅一行为一个正整数，表示被敲掉砖块的最大价值总和。

输入样例#1：

4 5
2 2 3 4
8 2 7
2 3
49

输出样例#1：

19