5487: 暑期营第三天 intetrals

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

设计一次竞赛使得选手最大可能的得分尽可能高。可供选择的题目共有N类,你可以从每一类题目中选出任意道题或不选组成一次竞赛。某一类题中的每一道题都需要相同的时间并能得到相同的分数。竞赛总时间不超过M 分钟

Input

第一行两个整数M,N分别表示竞赛总时间与题目类数;
第2到N+1行每行两个整数,分别表示这类题每一道的分数和所要时间,

Output

给定条件下最大可能的得分

Sample Input Copy

300 4
100 60
250 120
120 100
35 20

Sample Output Copy

605