说明

Kirk 有一个”理想“（并没有）， 就是以后能有一个属于自己水族馆。无奈啥啥都要钱，这让 Kirk 很烦恼，经过一大波的规划后，买了一大堆水族馆的设备，现在就差鱼还没有买了。可怜的Kirk兜里只剩下为数不多的 money，为了尽可能地让 Kirk 开心你能为 Kirk 制定一个卖鱼的方案，使得 cute 值拉满吗？

市场上的鱼有很多种，每种鱼有不同的价格（price）和可爱程度（cute）。

输入格式

第一行输入两个整数，money和kinds (0 <= money, kinds <= 1e4)，分别表示现有的总金和鱼的种类

接下来 kinds 行，每行两个整数 price.i 和 cute.i（0 <= price.i, cute.i <= 1e5），分别表示价格和这种价格的鱼对应的可爱程度

输出格式

输出一个整数，表示能获得的最大可爱程度

样例

20 3
2 1
5 3
7 5

13