烧桥计划

内存限制：512 MiB 时间限制：20 Sec

"经过精确的测量，整个桥梁可以被分为N段，从左往右标号1~N，每一段有一个'稳定值'来代表这一段的牢固程度-

-越牢固的地方，需要越大的代价去烧毁或拆毁，这个数列记为A1~An。这个稳定值介于1000~2000之间。详细的计

划分为两步：第一步，烧毁某些位置；第二步，拆掉某些位置。在第一步中，我们选择若干个位置，记为K个：Ap1

,Ap2,…,Apk，其中p1<p2<..<pk，然后逐一烧毁这些位置。由于放火是有危险的，所以对于从左往右的第i个位置p

i，烧毁它的代价为i*Api。现在，桥的剩下的N-K个位置被烧成了K+1段--可能有些段为空。对于每一段，如果它的

所有Ai之和不足M，那么说明这一段自己会坍塌，不必管它；否则，我们需要逐一拆毁这些位置，设这段Ai之和为T

，当T>M的时候我们就需要支付T的代价。两部分的代价加起来即为整个计划的总代价。整个计划一定会选取最优的

方案进行，也就是最小化总代价。目前记者还没有得到关于总代价的信息……不过全部的数据都有，你也可以自己

计算这个值。"

第一行是两个正整数N(<=100000)和M（<=2*10^8），含义如题目所述。

第二行是N个用空格隔开的正整数，代表整个A数列。（1000<=Ai<=2000）

一行一个正整数，之前所说的最小总代价。

N<=100000，1000<=Ai<=2000


			10 9

5 3 3 9 1 4 2 2 4 8


			17

【样例解释】

选择从左往右第3、5、9位置烧掉即可（下标从1开始标号）。

如果选择3、6、9，则总代价为33，明显不优。

#5424. 烧桥计划