0/1 Knapsack Problem

0/1 Knapsack Problem

Given item weights, values, and a capacity, maximize value without splitting items.

Input format

The first line contains N and CAP. The second line contains N weights (≤20). The third line contains N values (≤100).

Output format

Print the maximum value with capacity constraint.

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.

9 38
19 18 18 10 6 4 12 1 12
89 34 44 41 68 9 6 39 3

237

11 63
12 15 8 11 14 14 4 2 3 14 12
41 71 55 21 4 24 77 80 19 63 92

457