Rahul wants to set up bike factories in $$$N$$$ different Indian cities. Building a factory in the $$$i$$$-th city costs $$$c_i$$$ rupees per year and produces $$$n_i$$$ bikes annually. Rahul has a total budget of $$$C$$$ rupees per year.
What is the maximum number of bikes Rahul can produce annually, choosing any subset of cities, such that the total annual cost does not exceed $$$C$$$?
The first line contains two integers $$$N$$$ and $$$C$$$ ($$$1 \leq N \leq 1000$$$, $$$1 \leq C \leq 10^4$$$) — the number of cities and Rahul's yearly budget, respectively.
Each of the next $$$N$$$ lines contains two integers $$$c_i$$$ and $$$n_i$$$ ($$$1 \leq c_i \leq 10^4$$$, $$$1 \leq n_i \leq 10^6$$$), representing the cost and annual bike production of a factory in the $$$i$$$-th city.
Print a single integer — the maximum total number of bikes Rahul can produce in one year without exceeding the budget.
Input:
5 15 5 10 10 15 6 9 8 14 7 8
Output:
25
Input:
3 30 10 50 15 80 13 70
Output:
150
In the first test case, Rahul can choose factories from a subset of the cities such that the total cost does not exceed his budget of 15.
Let's evaluate a few possible combinations of cities:
Among these, the best is to choose City 1 and City 2 for a total cost of 15 and total production of 25, which is the maximum possible. Hence, Answer: $$$25$$$