Educational DP Contest AtCoder E - Knapsack 2

View as PDF

Points: 7
Time limit: 0.15s
Java 0.5s
Python 1.0s
Memory limit: 1G

Problem type

There are items, numbered . For each , item has a weight of and a value of .

Taro has decided to choose some of the items and carry them home in a knapsack. The capacity of the knapsack is , which means that the sum of the weights of items taken must be at most .

Find the maximum possible sum of the values of items that Taro takes home.

Constraints

• All values in input are integers.

Input Specification

The first line of input will contain 2 space separated integers, and .

The next lines will contain 2 space separated integers, and , the weight and value of item .

Output Specification

You are to output a single integer, the maximum possible sum of the values of items that Taro takes home.

Sample Input 1

3 8
3 30
4 50
5 60

Sample Output 1

90

Sample Input 2

1 1000000000
1000000000 10

Sample Output 2

10

Sample Input 3

6 15
6 5
5 6
6 4
6 6
3 5
7 2

Sample Output 3

17

Sample Explanations

For the first sample, items and should be taken. Then, the sum of the weights is , and the sum of the values is .

For the third sample, items , , and should be taken. Then, the sum of the weights is , and the sum of the values is .