0/1 Knapsack Problem

Mô tả

Cho n vật với trọng lượng và giá trị. Tìm tổng giá trị lớn nhất có thể mang với túi có sức chứa W.

Input Format

Dòng 1: n W.
Dòng 2: n số nguyên (giá trị).
Dòng 3: n số nguyên (trọng lượng).

Constraints

1 ≤ n ≤ 20
1 ≤ W ≤ 100
1 ≤ weight[i], value[i] ≤ 100

Sample Input

3 50
60 100 120
10 20 30

Sample Output

220