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
.
Comments