Description

成功的教育完了那个不诚实的小朋友后，阿童木兴奋的来到公司，结果老总连杯水都不给喝，直接拿出一份笔试试卷，“来，做完它，让我看看你是不是真的God like”。似乎老总还在为上次输给阿童木而暗暗生气。阿童木看着老总故意刁难的眼神，很是不服，来笔试绝对不能被“鄙视”。二话不说，开始做。刚接过试卷，阿童木就傻眼了，My god！贼多的题目，类型又多，分值又不相同，虽然自己全部都会做，但是在规定的时间内根本做不完，于是阿童木决定改变策略，在规定的时间内，挑选一些类型的题目，尽可能的得分。由于阿童木不知道该选哪些类型的题目，所以他用心灵感应向你求助。为了阿童木的工资，务必得帮帮他。 （特别提醒每种类型的题目只有一题）。

Input

* 第一行 ：规定的答题时间N(10000>=N>0)，题目的种类M(2000=>M>0)
* 接下来M行，每行包含两个整数，做出该类型的每道题目所要花费的时间T，做出该种类型题目得到的分数A。(10000>=T,A>0)

Output

* 输出在规定时间阿童木所能得到的最大分数。

Sample Input

300 4
100 60
250 120
120 100
35 20

Sample Output

180

HINT

Source