Optimal Task Assignment for Maximum Reward

Caesar commands a mercenary army of n individuals who work by taking various tasks from the Venice Merchant Guild. The tasks vary greatly; some require only one person while others require a team of several individuals. Each task has a specific requirement: if a task requires r workers, assigning exactly r workers yields the full reward R. However, if more than r workers are assigned (say p workers, with p > r), then the reward is reduced to \(\frac{R}{p - r + 1}\). Since assigning extra workers only diminishes the reward, it is always optimal to assign exactly r workers to a task if you choose to undertake it. Each mercenary can be assigned to at most one task, and tasks cannot share workers or have workers join or leave mid-task.

Given these constraints, Caesar wishes to assign his mercenaries to a subset of tasks (while possibly leaving some idle) such that the total reward is maximized. Your goal is to compute this maximum total reward. This problem reduces to selecting a subset of tasks such that the sum of the required workers does not exceed n, and the total reward is maximized. (This is essentially a knapsack problem.)

inputFormat

The first line contains two integers n and m (1 \(\le\) n \(\le\) 10⁴, 1 \(\le\) m \(\le\) 10³), representing the number of mercenaries and the number of tasks, respectively.

Each of the following m lines contains two integers r and R (1 \(\le\) r \(\le\) n, 1 \(\le\) R \(\le\) 10⁴), where r is the number of mercenaries required for the task and R is the reward provided if exactly r mercenaries are assigned.

outputFormat

Output a single integer: the maximum total reward that can be achieved by optimally assigning mercenaries to tasks under the given constraints.

sample

5 3
2 10
3 20
4 25

30