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

Submitting .cpp to 'coinbag'

You're not logged in! Click here to login

Compile Errors

Time Limit: 1 Seconds
Memory Limit: 256MB
No. of ACs: 120
Your best score: 0
Source: Dunjudge Archive

Subtask Score
1 100
2 0