A22629.敲砖块

提高+/省选-

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

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

14 15  4  3  23
 33  33 76  2
   2   13 11
     22 23
       31

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

你现在可以敲掉最多 mm 块砖,求得分最多能有多少。

输入格式

输入文件的第一行为两个正整数 nnmm;接下来 nn 行,描述这 nn 层砖块上的分值 ai,ja_{i,j},满足 0ai,j1000\leq a_{i,j}\leq 100

对于 100%100\% 的数据,满足 1n501\leq n\leq 501mn×(n+1)21\leq m\leq \frac{n\times(n+1)}{2}

输出格式

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

输入输出样例

  • 输入#1

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

    输出#1

    19
首页