0-1 Knapsack

You are given two lists of integers weights and values which have the same length and an integer capacity. weights[i] and values[i] represent the weight and value of the ith item.

Given that you can take at most capacity weights, and that you can only take at most one copy of each item, return the maximum amount of value you can get.

Constraints

• n ≤ 250 where n is the length of weights and values
• capacity ≤ 250

https://binarysearch.com/problems/0-1-Knapsack

Examples

Example 1

Input

• weights = [1, 2, 3]
• values = [1, 5, 3]
• capacity = 5

Output

• answer = 8

Solution