Contest Score (Inflate)

Problem Background

Special for beginners, ^_^

Problem Description

The more points students score in our USACO contest, the happier we are. We try to design our contest so people can score as many points as possible.

Now a contest will be held. The total time $T$ is fixed, and there are several types of problems to choose from. You may choose any number of problems of each type. Each type has a score $s_i$ (points earned) and a time $t_i$ (time needed). Choose some problems so that the total time does not exceed $T$ and the total score is maximized.

The input includes the contest time $M\ (1\le M\le 10000)$ and the number of problem types $N\ (1\le N\le 10000)$.

Each following line describes one "problem type" with two integers: the first is the points for solving this type ($1\le\text{points}\le 10000$), the second is the time needed ($1\le\text{minutes}\le 10000$).

Input Format

Line 1: two integers — the contest time $M$ and the number of problem types $N$.

Lines $2\sim N+1$: two integers each — the score and time of each problem type.

Output Format

A single line with the maximum score achievable within the given fixed time.

Sample Input

300 4
100 60
250 120
120 100
35 20

Sample Output

605

Constraints

$1\le M\le 10000$, $1\le N\le 10000$, $1\le\text{points}\le 10000$, $1\le\text{minutes}\le 10000$.

Time limit 1s, memory limit 1024KiB for each test case.

Hint

One way to reach 605: choose two problems of type 2 and three problems of type 4.