Welcome   HUNAN NORMAL UNIVERSITY ACM/ICPC Judge Online
 Home FAQs Pro Problem Set Practices Online Contests Major Exercises OI Special Judgement Submit Online Status User Ranklist Users Register new Login Web Links Hunan Normal University College of Information Science and Engineering
 Score Inflation Time Limit: 2000ms, Special Time Limit:5000ms, Memory Limit:32768KB Total submit users: 7, Accepted users: 6 Problem 10527 : No special judgement Problem description The more points students score in our contests, the happier we here at the HUNNU:ACM-ICPC are. We try to design our contests so that people can score as many points as possible, and would like your assistance. We have several categories from which problems can be chosen, where a "category" is an unlimited set of contest problems which all require the same amount of time to solve and deserve the same number of points for a correct solution. Your task is write a program which tells the Admin Mr qshj how many problems from each category to include in a contest so as to maximize the total number of points in the chosen problems while keeping the total solution time within the length of the contest. The input includes the length of the contest, M (1 <= M <= 10,000) (don't worry, you won't have to compete in the longer contests until training camp) and N, the number of problem categories, where 1 <= N <= 10,000. Each of the subsequent N lines contains two integers describing a category: the first integer tells the number of points a problem from that category is worth (1 <= points <= 10000); the second tells the number of minutes a problem from that category takes to solve (1 <= minutes <= 10000). Your program should determine the number of problems we should take from each category to make the highest-scoring contest solvable within the length of the contest. Remember, the number from any category can be any nonnegative integer (0, one, or many). Calculate the maximum number of possible points. Input Line 1:M, N -- contest minutes and number of problem classes Lines 2-N+1:Two integers: the points and minutes for each class Lines N+2:M, N -- Again,contest minutes and number of problem classes of another test case Lines N+3-...:Just as the first test case,two integers: the points and minutes for each class Lines ...:Other test cases,just as the first test case End of file Output For each test  case,a single line with the maximum number of points possible given the constraints. Sample Input 300 4 100 60 250 120 120 100 35 20 Sample Output 605 Problem Source jiyanmoyu Submit   Discuss   Judge Status  Problems  Ranklist

HUNAN NORMAL UNIVERSITY ACM/ICPC Judge Online, Version 2010.5.5.final.
Web visits:18329 today,16241320 total, since 2010-05-07