1748: 最大报酬

Memory Limit：128 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：74 Solved：52

Description

小明每周上班都会拿到自己的工作清单，工作清单内包含n项工作，每项工作都有对应的耗时时间（单位h）和报酬, 工作的总报酬为所有已完成工作的报酬之和，那么请你帮小明安排一下工作，保证小明在指定的工作时间内工作收入最大化。

Input

输入的第一行为两个正整数T，n。 T代表工作时长（单位h，0<T<1000000），n代表工作数量（1<n≤3000）。 接下来是n行，每行包含两个整数t，w。 t代表该工作消耗的时长（单位h，t>0）,w代表该项工作的报酬。

Output

输出小明制定工作时长内工作可获得的最大报酬。

Sample Input Copy 

40 3
20 10
20 20
20 5

Sample Output Copy 

30

Source/Category

SubmitSubmit RecordStatisticsShowOff!