Josephine was trying to stuff all her coins to a bag. Unfortunately, because her coins were
so big, she could not fit them into her bag. Even though she tried her best to squeeze a perfectly
solid coin, she did not succeed.
Write a program to help her decide which coins to fit into her bag.
Given n (1 ≤ n ≤ 500) coins of w[i] weight and v[i] value (0 ≤ w[i], v[i] ≤ 500), what is the maximum value
you can fit into a bag of size m (1 ≤ m ≤ 500)?
Points: 100
Input Format
Line 1: Two integers, n and m, representing the number of coins and the size of the bag.
Line 2...n: Two integers on each line, with the (i + 1)th line containing the weight w[i] and value v[i] of coin i.
Sample Input
3 5
5 2
2 1
3 2
Output Format
Line 1: A single integer which is the maximum value that can be fitted into the bag of size m.
Output
3
Output Details
The maximum value can be achieved with the two coins with weight 2 and value 1, and the coin with weight 3 and value 2.