Rahul and Bike Factories

mediumknapsackDP

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$$$?

Input Format:

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.

Output Format:

Print a single integer — the maximum total number of bikes Rahul can produce in one year without exceeding the budget.

Examples:

Example 1:

Input:

5 15
5 10
10 15
6 9
8 14
7 8

Output:

25

Example 2:

Input:

3 30
10 50
15 80
13 70

Output:

150

Note:

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:

  • Cities 1 and 2: cost $$$= 5 + 10 = 15$$$, production $$$= 10 + 15 = 25$$$
  • Cities 3 and 4: cost $$$= 6 + 8 = 14$$$, production $$$= 9 + 14 = 23$$$
  • Cities 3 and 5: cost $$$= 6 + 7 = 13$$$, production $$$= 9 + 8 = 17$$$
  • City 2 alone: cost $$$= 10$$$, production $$$= 15$$$
  • Cities 4 and 5: cost $$$= 8 + 7 = 15$$$, production $$$= 14 + 8 = 22$$$

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

Code

Loading Editor...