P2722 [USACO3.1] Score Inflation

The more points contestants score in our USACO contests, the happier we are. We try to design our contests so that people can score as many points as possible, and we need your help.

We can choose contest problems from several categories. Here, a "category" refers to a set of problems such that solving any problem in the set takes the same amount of time and yields the same score. Your task is to write a program to tell the USACO staff how many problems to select from each category so that the total time spent solving problems is within the contest time limit and the total score is maximized.

The first line contains two integers separated by a space, representing the contest duration $m$ and the number of categories $n$. Lines $2$ through $(n + 1)$ each contain two integers separated by a space. On line $(i + 1)$, the integers $p_i, t_i$ denote the score awarded for a problem in category $i$ and the time required to solve it. Since problems are grouped by category, you may select problems from the same category repeatedly.

Output a single integer, the maximum total score.

Constraints For $100\%$ of the testdata, it is guaranteed that $1 \leq n, m \leq 10^4$, and $1 \leq p_i, t_i \leq 10^4$. Translated by ChatGPT 5