题目描述

灰灰今天心情很好，在MPT管理群里有\(M\)个漂亮的女孩。灰灰很年轻，比较花心，所以灰灰非常喜欢他们。
但是灰灰不是活在古代，他不能一次娶所有女孩纸啊，因此灰灰每次只能挑选一个女孩纸结婚。与每个女孩子结婚，灰灰都能获得一些快乐。与第\(i\)的女孩纸结婚能获得\(a_i\)个快乐值。
因为灰灰比较花心，他与一个女孩纸结婚后过几年就会离婚然后追求其他女孩子，而被抛弃的女孩纸就会退群，灰灰无法再与他相处。
已知第\(i\)个女孩纸会与灰灰一起生活\(b_i\)年，给定灰灰的大限\(N\)，因为灰灰不会算法，所以请你帮他算一下如何结婚才能获得最多的快乐值。

输入格式

第一行两个整数，\(N\)与\(M\)，分别表示灰灰的大限与女孩纸个数
接下来\(M\)行，每行两个整数\(a\)与\(b\)，分别表示与这个女孩结婚能获得的快乐值和相处时长

输出格式

一个整数，表示能获得的最大快乐值

样例

输入

15 5
1 5
3 6
5 8
2 5
3 6

输出

8

数据范围

对于\(100\%\)的数据，\(M \leqslant 100\)

保证 \(\sum_{i = 1}^{n}{a_i}\) 在 int 范围内