竞赛总分(inflate) 【问题描述】 学生在我们 USACO 的竞赛中的得分越多我们越高兴。我们试着设计我们的竞赛以便人们 能尽可能多得分。 现在要进行一次竞赛，总时间 T 固定，有若干类型可选择

竞赛总分(inflate)dlT100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【问题描述】dlT100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
学生在我们 USACO 的竞赛中的得分越多我们越高兴。我们试着设计我们的竞赛以便人们dlT100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
能尽可能多得分。dlT100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
现在要进行一次竞赛，总时间 T 固定，有若干类型可选择的题目，每种类型题目可选入dlT100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
的数量不限，每种类型题目有一个 si（解答此题所得的分数）和 ti（解答此题所需的时间），dlT100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
现要选择若干题目，使解这些题的总时间在 T 以内的前提下，所得的总分最大。dlT100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输入包括竞赛的时间 M(1 <= M <= 10000)和题目类型数目 N(1 <= N <= 10000)。dlT100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
后面的每一行将包括两个整数来描述一种"题型":dlT100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
第一个整数说明解决这种题目能得的分数(1 <= points <= 10000),第二整数说明解决dlT100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
这种题目所需的时间(1 <= minutes <= 10000)。dlT100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【输入格式】dlT100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
第 1 行: 两个整数：竞赛的时间 M 和题目类型数目 N。dlT100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
第 2-N+1 行: 两个整数：每种类型题目的分数和耗时。dlT100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【输出格式】dlT100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
单独的一行，在给定固定时间里得到的最大的分数。dlT100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【样例输入】dlT100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
300 4dlT100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
100 60dlT100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
250 120dlT100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
120 100dlT100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
35 20dlT100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【样例输出】dlT100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
605 //从第 2 种类型中选两题和第 4 种类型中选三题