Maximize Reward Under Budget Constraint

You are given a budget \(B\) and a list of cities, where each city is represented as a pair of integers \( (c, r) \), with \(c\) being the cost to invest in that city and \(r\) being the reward obtained. Your task is to choose a subset of these cities such that the total cost does not exceed the budget \(B\) and the total reward is maximized.

This problem can be solved using a classic 0/1 knapsack dynamic programming approach. Let \(dp[i]\) denote the maximum reward obtainable using a budget of \(i\). The recurrence relation is given by:

[ \text{dp}[i] = \max\left{ \text{dp}[i],; \text{dp}[i-c] + r \right} \quad \text{for each city with cost } c \text{ and reward } r \text{ and for } i \ge c. ]

Implement a program that reads the input from standard input (stdin) and writes the result (the maximum reward) to standard output (stdout).

inputFormat

The input is given on standard input as follows:

1. The first line contains one integer \(B\) representing the available budget.
2. The second line contains one integer \(n\) representing the number of cities.
3. The following \(n\) lines each contain two integers \(c\) and \(r\), where \(c\) is the cost of the city and \(r\) is the reward.

outputFormat

Output a single integer: the maximum total reward obtainable without exceeding the budget \(B\).

300
3
150 70
200 90
120 60

130