【试题描述】

我们把YDSCO竞赛的试题分为若干类，每类都有足够多的题目，这些题目分值相同，耗时也相同。你的任务是编写一个程序决定每类题目应选择几道，使得考生在给定的时间内能得到尽可能多的分数。

【输入要求】

• 第一行：包括两个整数M,N。M(1 ≤ M ≤ 10,000)代表竞赛的时间(min)，N（1 ≤ N ≤10,000）代表问题种类的数目

• 第2..N+1行：包括两个整数--每类题目的分值(1 ≤ 分值 ≤ 10000)和耗时(1 ≤耗时≤ 10000)

【输出要求】

最大可能得到的分数

【输入样例】

300 4

100 60

250 120

120 100

35 20

【输出样例】

605