HZNUOJ

Little Sub and Piggybank

Tags:     x/0 = oo   dp大法
Time Limit:  1 s      Memory Limit:   256 MB
Submission:632     AC:105     Score:94.32

Description

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.

Input

The first line contains one positive integer n(1 ≤ n ≤ 2000).

The second line contains n integers Wi(0 ≤ Wi ≤ 10^6).

The third line contains n integers Vi(0 ≤ Vi ≤ 10^6).

Samples

input
4 0 2 4 1 0 4 3 1
output
5

Author

CHEN, Jingbang