敲砖块

题目描述:

在一个凹槽中放置了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]<= 100。

输出格式:

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

样例输入:

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。

时间限制: 1000ms
空间限制: 128MB

---