1398 - Energy Balls

Time Limit : 5 Second

Memory Limit : 128 MB

Submission: 90

Solved: 24


       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:

  1. If the man's current energy is CE, then the maximum length he can dive is CE meters.

  2. The man can't get the energy of the balls he collect at each diving until he return to the lake surface.

  3. The man's initially has E units energy.

  4. You are guaranteed that the man can collect all the N energy balls after all.


        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 231


        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
© 2015 HUST ACMICPC TEAM. All Right Reserved.