说明

梦之队是学校田径队的精英,现在要参加市里组织的自由组合跑比赛,比赛要求是比赛委员会临时给的时间段中,自由选择至少一员动动员参加,但是每个动动员的参赛时间都是一定的且不一定相同,而且每个学校的参加队员只能在指定的时间段里参加跑步,即整个学校的参赛时间不能超过这个时间段.现在已知道了每个动动员在指定的时间里可以跑多少米了,如果你是教练,你将选择哪些运动员来参加比赛,使学校梦之队的总成绩(跑的距离多少米)为最大?对于30%的数据，M <= 10；对于全部的数据，M <= 100。

输入格式

第一行有两个整数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