【题目描述】

在一个凹槽中放置了N层砖块，最上面的一层有N块砖，从上到下每层依次减少一块砖。每块砖都有一个分值，敲掉这块砖就能得到相应的分值，如图所示。

砖块的相应分值

如果你想敲掉第i层的第j块砖的话，若i=1，你可以直接敲掉它；若i>1，则你必须先敲掉第i-1层的第j和第j+1块砖。

你现在可以敲掉最多M块砖，求得分最多能有多少。

【输入文件】

输入文件第一行有两个正整数N和M； 接下来的N行，描述这N层砖块上的分值A[i，j]，满足0<=A[i，j]<=l00。

【输出文件】

仅一行，包含一个整数，为最大的得分。

【样例输入】

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

【样例输出】

19

【数据规模】

对于20%的数据，满足1≤N≤10，1≤M≤30；

对于100%的数据，满足1≤N≤50，1≤M≤500。