1398  Energy Balls
Time Limit : 5 Second
Memory Limit : 128 MB
Submission: 90
Solved: 24
 Description
One day, a man came to the world's deepest lake. There are N energy balls in the lake. And the first ball is at 100m deep, the second ball at 200m deep......, and the Nth ball is at N * 100 meters deep. At each time i, the man takes a diving into D[i] meters deep and collects the energy balls along the path from the lake surface to the D[i] meters deep.
Each dive of X meters deep costs X units of energy, if the ith ball was collected, it would provide the man W[i] units of energy, then the ith energy ball was gone.
You are to calculate the maximum units of energy the man left after collecting all the N balls.
Note that:
If the man's current energy is CE, then the maximum length he can dive is CE meters.
The man can't get the energy of the balls he collect at each diving until he return to the lake surface.
The man's initially has E units energy.
You are guaranteed that the man can collect all the N energy balls after all.
 Input
There are multiple test cases. For each case:
The first line is two integer N, E (the number of energy balls, the initial energy of the man) (1 <= N <= 2,000,000)
The next line contains N number representing W[i]. the sum of W[i](1 <= i <= N) is less than 2^{31}
 Output
For each case, output the maximum units of energy the man left after collecting all the N balls.
Input data will guarantee that at least one solution exists.
 sample input

3 200 200 200 200
 sample output

400
 hint
 source
 Orz教主第4次模拟赛