1491: 金字塔
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：41
解决：25
题目描述
小X来到一个雄奇的金字塔挖宝，但是这是一座被诅咒的金字塔，小X必须马上逃离这里，否则小X就会被埋在金字塔里，但他不希望此行落空。
现在小X面前有N+1种财宝，每种财宝都有一个价值。第一种财宝重量为0，第二种财宝重量为1，总之第I种财宝重量为I-1。现在小X希望拿走N+M个物品，但是这M+N个物品总重量不能超过N。小X希望能获得最大的价值。你能帮帮他吗？
由于金字塔跟小X一样牛，所以每种财宝无限个。
输入
第一行两个正整数N，M
第二行N+1个整数，第I个整数代表了第I种财宝的价值
输出
一个数，表示最大利润。
样例输入 复制
5 3
4 7 2 5 -3 6
样例输出 复制
47提示
数据范围：
10%满足N,M<=10
40%满足N,M<=100
100%满足 N,M<=3000 abs(财宝价值)<=1000