4318: 敲砖块
Memory Limit：128 MB
Time Limit：1 S
Judge Style：Text Compare
Creator：
Submit：23
Solved：8
Description
在一个凹槽中放置了N层砖块，最上面的一层有N块砖块，从上到下每层依次减少一块砖。每块砖都有一个分值，敲掉这块砖就能得到相应的分值，如图
如果你想敲掉第i层的第j块砖的话，若i=1,你可以直接敲掉它，若i>1,则你必须先敲掉第i-1层的第j和第j+1块砖。
你现在可以敲掉最多M块砖，求得分最多能有多少。
Input
输入文件第一行有两个整数N和M；
接下来的N行，描述这N行砖块上的分值A[i,j],满足0<=A[i,j]<=100.
Output
仅一行，包含一个整数，为最大的得分。
Sample Input Copy
4 5
2 2 3 4
8 2 7
2 3
49
Sample Output Copy
19HINT
对于20%的数据，满足1<=N<=10,1<=M<=30;
对于100%的数据，满足1<=N<=50,1<=M<=500.