Maximize Impression Value - Inmobi Online Assessment IIT BHU

Problem Preview

"You are given n ad impressions. Each impression has a value and a cost (floor price). You have a fixed budget B. Your task is to select a subset of impressions such that the total cost does not exceed B, while maximizing the total value of the selected impressions. Input Format The first line contains two integers n and B — the number of impressions and the available budget. The next n lines each contain two integers: value — the value of the impression. cost — the cost (floor price) of the impression. Output Format Print a single integer — the maximum total value that can be obtained without exceeding the budget. Constraints 1 ≤ n ≤ 1000 1 ≤ B ≤ 10^5 1 ≤ value ≤ 10^9 1 ≤ cost ≤ 10^5 Sample Input 4 10 10 5 40 4 30 6 50 3 Sample Output 90 Explanation Select the 2nd and 4th impressions: Total Cost = 4 + 3 = 7 (within the budget of 10) Total Value = 40 + 50 = 90 No other valid selection yields a higher total value."