Cool

Grade Open Time Friday, 19 September 2014, 10:08 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:08 am
Allow late Yes Close Time Friday, 26 September 2014, 10:08 am
Input file cool.in Output file cool.out

【题目描述】


Tky来到一个雄奇的金字塔挖宝,但是这是一座被诅咒的金字塔,Tky必须马上逃离这里,否则Tky就会被埋在金字塔里,但他不希望此行落空。

 现在Tky面前有N+1种财宝,每种财宝都有一个价值。第一种财宝重量为0,第二种财宝重量为1,总之第I种财宝重量为I-1。现在Tky希望拿走N+M个物品,但是这M+N个物品总重量不能超过N。Tky希望能获得最大的价值。你能帮帮他吗?

由于金字塔跟Tky一样牛,所以每种财宝无限个。


【输入格式】


第一行两个正整数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


【来源】

在此键入。