同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

22073_敲砖块

2022-5-16 18:21| 发布者: Hocassian| 查看: 22| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-4-8950688102700-Problem List-采集的数据-后羿采集器.html

Pro.ID

22073

Title

敲砖块

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=22073

AC

Submit

Ratio

4.17%

时间&空间限制

Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others)

描述

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

如果你想敲掉第i层的第j块砖的话，若i=1，你可以直接敲掉它；若i>1，则你必须先敲掉第i-1层的第j和第j+1块砖。

现在你可以敲掉最多M块砖，求得分最多能有多少？

输入

输入文件第一行有两个正整数N和M； 1 <= N <= 50 , 1 <= M <= 500

接下来N行，描述这N层砖块上的分值 A[i,j] ，满足 0 <= A[i,j] <= 100 。

输出

Description

如果你想敲掉第i层的第j块砖的话，若i=1，你可以直接敲掉它；若i>1，则你必须先敲掉第i-1层的第j和第j+1块砖。

现在你可以敲掉最多M块砖，求得分最多能有多少？

Input

输入文件第一行有两个正整数N和M； 1 <= N <= 50 , 1 <= M <= 500

接下来N行，描述这N层砖块上的分值 A[i,j] ，满足 0 <= A[i,j] <= 100 。

Output

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

Sample Input

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

Sample Output

Author

John

样例输入