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 ≤ 108), the number of items, and the size of the knapsack. The second line contains n integer with the i-th integer being vi (1 ≤ vi ≤ 107), the values of i-th item. Third line describes the sizes of items si (1 ≤ si ≤ 107) in the same format.
It is guaranteed that in each test either B ≤ 50000 or max1 ≤ i ≤ n vi ≤ 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