背景

为了即将到来的蓝桥杯省赛，小方小块小鸟都在密锣紧鼓的训练。他们根据自己的情况进行专项练习，要么做一些基础知识巩固的题单，要么做某类问题的加强训练。他们觉得在下半学期里以此作为阶段性的学习目标拼一拼，就和在校运会前特意训练一样有趣。通过自己的努力让自己越来越厉害、意志力越来越强，是比奖项、名次重要得多得多得多的收获。

描述

小方小块小鸟在做题的时候，就发现，原来备赛和平常的学习不太一样呢。由于比赛举行的时间是确定的，能利用起来进行做题的时间就基本不能变化啦。知道了这一点，在备赛的时间里选择做怎样的题，就比较讲究了。以备赛为目标的话，自己的基础和掌握程度不一样，做每道题的收益就不一样。比如，基础薄弱的同学，做基础题的收益就大，提高题的收益就小一些，因为把基础赶上去，比赛的时候就能把前面的题目稳稳拿住；而对于基础扎实，做完前三题还有一个小时以上的同学，做提高题就是更大收益的事情了，因为比赛里面，基础题就那么几道，后面的题都是要上难度的呀。

知道了这一点，小方小块小鸟在制作刷题计划的时候，就请求老师帮忙，定出他们完成每个题目的收益$gain$和估计需要的时间$time$。随后他们根据自己的安排，分别计划在比赛前投入$total\_time$进行备赛。请你编写程序，帮他们收益最大的做题计划，然后输出这个最佳计划的收益。

输入输出格式

输入

若干行，其中，第二行为一个正整数$total\_time$，表示能投入的备赛时间。（ $1≤ total\_time ≤ 10,000$ )

第二行为一个正整数$N$，表示老师帮忙完成收益、预估时间的题目数量。 （ $1≤ N ≤ 10,000$ )

随后N行，每行两个以空格分割的正整数，分别表示某个题目的收益$gain$和预估时间$time$。 （ $1≤ gain ≤ 10,000, 1≤ time ≤ 10,000$ ）

输出

一行，为最佳计划的总收益。

样例

50
3
20 20
30 30
45 40

50

样例一说明

可以投入的备赛时间为50，一共有3个题，最佳计划应该是做第1、2个题目，共花费时间50，(20+30)，收益50。注意，这个计划比只做第3题有更大的收益。