794. 0-1 Knapsack
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?
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 a single integer representing the maximum value that can be obtained by optimally choosing the items.
5 4 1 2 3 2 2 8 4 0 5 3
1 <= S,N <= 1000