← 返回题目
题库练习 敲砖块
← 上一题 下一题 →

A2915 | 敲砖块

来源2004
时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

在一个凹槽中放置了 $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
C++ 编辑器
输入
输出