794. 0-1 Knapsack
0
Medium
You are preparing for a beach vacation and can only bring one bag with a maximum capacity of S (1 <= S <= 1000).
You have N (1 <= N <= 1000) items that you may want to bring with you.
However, not all items can fit in the bag, so you need to choose wisely.
Each item has a size and a value.
Your goal is to maximize the total value of the items you bring.
What is the maximum total value you can achieve?
Input Format
The first line contains two integers, N and S, separated by a space.
The second line contains N space-separated integers, representing the sizes of the items.
The third line contains N space-separated integers, representing the values of the items.
Output Format
Output a single integer representing the maximum value that can be obtained by optimally choosing the items.
Example
Input
5 4
1 2 3 2 2
8 4 0 5 3
Output
13
Constraints
1 <= S,N <= 1000
Loading...
View Submissions
Console