#P1017. Buy Fish

Buy Fish

说明

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