10552: 打砖块_1

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

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

你的任务是从一个有n（n<=50）层的砖块堆中，敲掉(m<=500)块砖，使得被敲掉的这些砖块的价值总和最大。

你将从文件中读入数据，数据的第一行为两个正整数，分别表示nm，接下来的第i每行有n-i+1个数据，分别表示a[i1]a[i2]……a[in – i + 1]。

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