Time Limit: 5s
Memory Limit: 128MB
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:
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}
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.
3 200 200 200 200
400