## A Knapsack Problem

View as PDF

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

Author:
Problem type

You found pieces of gold ore in a cave, each of which has weight kg, and value . Since you are not that strong, you can only bring back 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 .

The next lines will each contain two integers, .

#### 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