Description
A new supermarket has opened in Bikini Bottom!
Since the supermarket has just opened, the fruit section is having a sale: given a basket, you can fill it with any kind and any amount of fruit. No matter what you have chosen, the whole basket of fruit costs 10 dollars, as long as the basket can bear the weight.
Squidward has made Spongebob and Patrick buy some fruit in this sale for him, please help them figure out the maximum value they could get.
There are only n kinds of fruit left. Each of them has its weight and value. The value of the whole basket of fruit is the sum of the value of each kind of fruit. Squidward only wants to eat at most one unit for each kind of fruit.
Input
The first line contains an integer n, representing the remaining number of fruit.
The second line contains n integers w1, w2 ... wn. Represent each kind of fruit's weight per unit.
The third line contains n integers v1, v2 ... vn. Represent each kind of fruit's value per unit.
The last line contains an integer W, the maximum weight a basket could bear.
Constraints:
1 ≤ n ≤ 20
1 ≤ wi, vi, W ≤ 107, ∀i ∈ [1, n]
Output
Output the maximum value of the basket that Spongebob and Patrick could get.