ExpertAlgorithms50 points

Spend the ad budget for the most leads

A marketing manager at an e-commerce start-up in Jakarta has a fixed monthly budget and a list of possible campaigns. Each campaign has a fixed cost and a forecast number of new leads. A campaign can be bought at most once and cannot be bought partially. She wants the combination of campaigns that brings the most leads without spending more than the budget.

Task: the first line holds n and B (1 ≤ n ≤ 60, 0 ≤ B ≤ 300). Each of the next n lines holds cost leads (cost from 1 to 300, leads from 0 to 1000). Print the maximum total number of leads achievable with total cost at most B.

Sample test

Input

4 50
10 60
20 100
30 120
25 90

Expected output

220

Your answer is also checked against 5 hidden tests.

Need a hint?

Build the answer for every budget from 0 up to B, adding one campaign at a time.