Description

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

Input Format

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

Output Format

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

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

133

Source

动态规划 背包问题