I :: 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⁸), 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⁷), the values of i-th item. Third line describes the sizes of items s_i (1 ≤ s_i ≤ 10⁷) 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
15

Submit

Source: 4th Kashan University's ACM Contest