Description

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.

Input Format

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 Format

Output a single integer, the maximum total score.

300 4
100 60
250 120
120 100
35 20

605

Hint

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