A Knapsack Problem

View as PDF

Submit solution

Points: 7
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type

You found N pieces of gold ore in a cave, each of which has weight w_i kg, and value v_i. Since you are not that strong, you can only bring back W kg of gold ore. You want to maximize the sum of the values of the pieces of gold ore you bring back up. What is the maximum possible sum?

Input Specification

The first line will contain two integers N, W\ (1 \le N, W \le 1\ 000).

The next N lines will each contain two integers, w_i, v_i\ (1 \le w_i, v_i \le 1\ 000).

Output Specification

Output the maximum possible sum of the value of the pieces of gold ore you bring back to the surface.

Sample Input 1

3 3
1 1
2 2
3 4

Sample Output 1

4

Sample Input 2

3 11
11 10
5 3
6 6

Sample Output 2

10

Comments

There are no comments at the moment.