Little Sub has a very special piggybank.
Every day i, the supermarket will sell a set of special candies which is only available at that specificday. It costs W [i] and will bring V [i] happiness to Little Sub.

However, Little Sub can buy the candy set only when there is exactly W [i] money in his piggybank.

If he chooses to buy it, the piggybank will be empty again.

Initially, there is no money in the piggybank. Little Sub can put any real number amount of money into it everyday before he decides whether to buy the candy. What’s more, one condition he should follow is that he cannot put more money into the piggybank than yesterday. One special example is that if you don’t put money into the piggybank this time, you cannot put money into the piggybank anymore.

Now we have already know the selling plan in the following n days and the piggybank is empty now. Please help Little Sub to maximize the happiness he gets.