打砖块(brike)

题号：NC210249
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

在一个凹槽中放置了 $\ n$ 层砖块，最上面的一层有 $\ n$ 块砖，第二层有 $\ n-1$ 块，……最下面一层仅有一块砖。第 $\ i$ 层的砖块从左至右编号为 $1，2,\dots i$ ，第i层的第j块砖有一个价值 $a[i,j]（a[i,j]\leq 50）$ 。下面是一个有5层砖块的例子：

如果你要敲掉第 $\ i$ 层的第 $\ j$ 块砖的话，若 $\ i=1$ ，你可以直接敲掉它，若 $\ i>1$ ，则你必须先敲掉第 $\ i-1$ 层的第j和第 $\ j+1$ 块砖。
你的任务是从一个有 $n（n\leq 50）$ 层的砖块堆中，敲掉 $(m\leq 500)$ 块砖，使得被敲掉的这些砖块的价值总和最大。

输入描述:

数据的第一行为两个正整数，分别表示 ，接下来的第i每行有 个数据，分别表示。

输出描述:

第1行：表示被敲掉砖块的最大值总和

示例1

输入

复制

输出

复制

备注:

对于20%的数据，满足;
对于100%的数据，满足;