#1476. 分数膨胀(递归,小数据)

分数膨胀(递归,小数据)

【试题描述】

我们把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