问题 22900 --竞赛总分

22900: 竞赛总分

时间限制: 1 Sec  内存限制: 128 MB
提交: 9  解决: 7
[提交][状态][讨论版][数据上传:][下载FPS1元][添加到购物车][下载测试数据1元][92kb]

题目描述

学生在我们USACO的竞赛中的得分越多我们越高兴。我们试着设计我们的竞赛以便人们能尽可能的多得分。现在要进行一次竞赛,总时间T固定,有若干类型可选择的题目,每种类型题目可选入的数量不限,每种类型题目有一个si(解答此题所得的分数)和ti(解答此题所需的时间),现要选择若干题目,使解这些题的总时间在T以内的前提下,所得的总分最大。
输入包括竞赛的时间,M(1 <= M <= 10000)和题目类型数目N(1 <= N <= 10000)。
后面的每一行将包括两个整数来描述一种"题型":
第一个整数说明解决这种题目能得的分数(1 <= points <= 10000),第二整数说明解决这种题目所需的时间(1 <= minutes <= 10000)。

输入

第 1 行: 两个整数:竞赛的时间M和题目类型数目N。 第 2-N+1 行: 两个整数:每种类型题目的分数和耗时。

输出

单独的一行,在给定固定时间里得到的最大的分数。

样例输入

300 4
100 60
250 120
120 100
35 20

样例输出

605

提示

来源

[提交][状态]