问题描述

具体描述见教材p246： “梦之队”要参加市里组织的自由组合跑比赛，在比赛委员会临时给定的时间段中，各队自由选择至少一名动员参加，但是每个运动员的参赛时间都是一定的且不一定相同，而且每个学校的参赛队员只能在指定的时间段里参加跑步，即整个学校的参赛时间不能超过这个时间段。现在已经知道了每个运动员在指定的时间里可以跑多少米，如果你是教练，你将选择哪些运动员参加比赛，使学校“梦之队”的总成绩(跑的距离多少米)最高?

格式

输入

第1行有两个整数 S(1≤S≤1000) 和 n(1≤n≤100)，用一个空格隔开，S代表学校参赛队的总共跑步的时间，n代表可选择的运动员数目。接下来的2~n+1行，每行包括两个在1到100之间 (包括1和100) 的整数，分别是一名运动员的可跑时间和在这个时间段里的成绩。

输出

一个整数，表示在规定的时间内，“梦之队”可得到的最高成绩。

样例

100 5
77 92
22 22
29 87
50 46
99 90

133

限制

1s, 64MB.