题目描述

“梦之队”要参加市里组织的自由组合接力跑比赛，在比赛委员会给定的时间段中，各队自由选择至少一名运动员参加，但是每个运动员的参赛时间都是一定的且不一定相同，而且每个学校的队员只能在指定的时间段里完成跑步，即每个参赛运动员的时间之和不能超过整个学校的总跑步时间。

现在已知道了每个运动员在指定的时间里可以跑多少米，如果你是教练，你将选择哪些运动员参加比赛。使学校学“梦之队”的接力跑总成绩（跑的距离多少米）最高？

输入格式

第 1 行有两个整数 S（1 ≤ S ≤ 1000）和 n（1 ≤ n ≤ 100），用一个空格隔开，S 代表学校参赛队的总共跑步的时间，n 代表可选择的运动员数目。

接下来的 2 至 n+1 行，每行包括两个在 1 到 100 之间（包括 1 和 100）的整数，分别是一名运动员的可跑时间和在这个时间段里的成绩。

输出格式

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

样例

4 3
4 30
3 20
1 11

31

如果一个运动员没有跑完，只跑了一半，则他的成绩不会被计算