g6-08133. 限时测验 未做

一场限时测验共有 $n$ 类题目，总时长为 $M$ 分钟。第 $i$ 类题目每答对一道得 $p_i$ 分、要花 $t_i$ 分钟；每类题的数量都足够多，可以反复做。

小林想在这 $M$ 分钟里拿到尽可能多的分数，求他最多能得多少分。

第一行两个整数 $M$、$n$，分别表示测验总时长与题目种类数。

接下来 $n$ 行，每行两个整数 $p_i$、$t_i$，依次表示该类题目每题的得分与耗时。

一行一个整数，表示最多能得到的总分。

输入 1

10 2
5 3
6 4

输出 1

16

第 $1$ 类做 $2$ 道，花 $3\times 2=6$ 分钟得 $5\times 2=10$ 分；第 $2$ 类做 $1$ 道，花 $4$ 分钟得 $6$ 分。合计 $10$ 分钟、$16$ 分。

$1\le n\le 1000$，$0\le M\le 2\times 10^4$，$1\le t_i\le 10^4$，$1\le p_i\le 10^4$。保证答案不超过 $10^{18}$。