1627: 敲砖块

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

如果你想敲掉第i层的第j块砖的话，若i=1，你可以直接敲掉它；若i>1，则你必须先敲掉第i-1层的第0j和第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