[HNOI2004] 敲砖块

题目背景

题目描述

在一个凹槽中放置了 $n$ 层砖块、最上面的一层有 $n$ 块砖,从上到下每层依次减少一块砖。每块砖都有一个分值,敲掉这块砖就能得到相应的分值,如下图所示: ```cpp 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\leq a_{i,j}\leq 100$。 对于 $100\%$ 的数据,满足 $1\leq n\leq 50$,$1\leq m\leq \frac{n\times(n+1)}{2}$;

输出格式


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

输入输出样例

输入样例 #1

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

输出样例 #1

19