问题 22583 --跳跃忍者

22583: 跳跃忍者

时间限制: 1 Sec  内存限制: 128 MB
提交: 92  解决: 17
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][24192kb]

题目描述

    跳跃忍者很能跳,因此他很嘚瑟。他每次跳需要消耗能量,每跳1米就会消耗1点能量,如果他有很多能量就能跳很高。

    他为了收集能量,来到了一个神秘的地方,这个地方凡人是进不来的。在这里,他的正上方每100米处就有一个能量球(也就是这些能量球位于海拔100,200,300……米处),每个能量球所能提供的能量是不同的,一共有N个能量球(也就是最后一个能量球在N×100米处)。他为了想收集能量,想跳着吃完所有的能量球。他可以自由控制他每次跳的高度,接着他跳起把这个高度以下的能量球都吃了,他便能获得能量球内的能量,接着吃到的能量球消失。他不会轻功,也不会二段跳,所以他不能因新吃到的能量而变化此次跳跃的高度。并且他还是生活在地球上的,所以每次跳完都会掉下来。

    问跳跃忍者若要吃完所有的能量球,最多还能保留多少能量。



输入

    第1行包含两个正整数N,M,表示了能量球的个数和跳跃忍者的初始能量。

    第2行包含N个非负整数,从左到右第I个数字依次从下向上描述了位于I×100米位置能量球包含的能量,整数之间用空格隔开。


    对于10%的数据,有N≤10;
    对于20%的数据,有N≤100;
    对于40%的数据,有N≤1000;
    对于70%的数据,有N≤100000;
    对于100%的数据,有N≤2000000。

    保证对于所有数据,跳跃忍者都能吃到所有的能量球,并且能量球包含的能量之和不超过2^31-1。


输出

    仅包括一个非负整数,为跳跃忍者吃完所有能量球后最多保留的能量。

样例输入

3 200
200 200 200

样例输出

400

提示

来源

[提交][状态]