# Interesting knapsack

Time Limit: 4 Seconds Memory Limit: 65536 KB

Knapsack is well-known optimization problem. In 0-1 version of problem, you are given a list of n items each with a size and a value, and a bag of size B, you choose a subset of items that fit in the bag and their total value is maximized. This problem is proved to be NP-hard, but it has pseudo-polynomial time dynamic programming algorithm.

In this problem you should solve the exact same problem with one additional constraint: either your bag is relatively small or the maximum value of items is limited.

## Input

Input contains at most 50 tests. The first line of each test contains n, B (1 ≤ n ≤ 100,1 ≤ B ≤ 10^{8}), the number of items, and the size of the knapsack. The second line contains n integer with the i-th integer being v_{i} (1 ≤ v_{i} ≤ 10^{7}), the values of i-th item. Third line describes the sizes of items s_{i }(1 ≤ s_{i} ≤ 10^{7}) in the same format.

It is guaranteed that in each test either B ≤ 50000 or max_{1 ≤ i ≤ n} v_{i} ≤ 500.

Input terminates with a line "`0 0`

".

## Output

For each test you should output a single line, the maximum total value of items in the knapsack.

## Sample Input

2 100000 1 500 1 100000 3 10 3 5 7 4 6 7 5 100 1 2 3 4 5 5 4 3 2 1 0 0

## Sample Output

500 8 15Submit

Source: 4th Kashan University's ACM Contest