Unbounded Knapsack Problem

Unbounded Knapsack Problem

Given item weights and values with unlimited supply, maximize value within a given capacity.

Input format

The first line contains N and CAP. The second line contains N weights. The third line contains N values.

Output format

Print the maximum value with unbounded items (can use each item multiple times).

Constraints

• Values fit in a 64-bit signed integer
• Trailing whitespace and a trailing newline are ignored by the judge

Read from stdin, write to stdout. Sample cases below show the exact format.

2 25
12 15
39 13

78

12 15
9 12 4 4 13 20 11 7 1 6 13 6
10 3 36 13 46 9 4 18 38 31 7 43

570