Herb Picking Challenge

LiYuxiang dreams of becoming the greatest physician in the world. To test his potential, a venerable doctor has led him into a cave filled with various herbs. Each type of herb requires a certain time to pick and has its own value. LiYuxiang is given a total amount of time, and in that time he can pick any number of herbs from any type (each type can be picked unlimited times). His goal is to maximize the total value of all the herbs he collects.

Formally, you are given a total time T and N types of herbs. For each herb type i, picking it takes t_i time and gives a value v_i. You can pick each type any number of times. Find the maximum total value that can be achieved within time T.

The problem can be modeled as an unbounded knapsack problem. In mathematical form, if we let dp[x] be the maximum value achievable in time x, then the recurrence can be written as:

[ dp[x] = \max_{1 \le i \le N ;\text{and}; t_i \le x} { dp[x-t_i] + v_i } ]

with the initial condition dp[0] = 0.

inputFormat

The first line contains two integers T and N, where T (0 \le T \le 10⁴) is the total available time and N (1 \le N \le 10³) is the number of herb types.

Then follow N lines, each containing two integers t_i and v_i (1 \le t_i, v_i \le 10⁴), representing the picking time and value of the i-th herb.

outputFormat

Output a single integer representing the maximum total value that can be achieved within time T.

sample

10 3
2 3
3 4
4 5

15