T202674 原神：原石的优惠大礼包【升级版】

米哈游公司下的著名开发世界冒险类游戏——原神，正迎来发行一周年的庆典活动，正因如此，瞧中商机的黄牛们纷纷通过自己的渠道屯了大量比官方更低价的且有限的原石。 --- 黄牛们经过派蒙的一番操作后，吸取了教训，他们联合在了一起，统一出售原石，并且用了一种新的销售方式——组合销售，即原石数量为 $p$ 的价格为 $x$。 派蒙上一次已经买到了足够的原石，虽然很想再宰黄牛们一笔，但因为经费有限，派蒙这次只有 $N$ 元。

第一行有 $2$ 个整数 $N$（$1 \le N \le 1000$）和 $M$（$1 \le M \le 100$），用一个空格隔开，$N$ 代表经费，$M$ 代表黄牛们有多少种组合销售。 接下来的 $M$ 行每行包括两个在 $1$ 到 $100$ 之间（包括 $1$ 和 $100$）的整数，分别表示购买某种组合需要支付的费用和这组合能得到的原石数量。

输出可以买到的原石的最大数量。

**【数据范围】** - 对于 $30\%$ 的数据，$M \le 10$； - 对于全部的数据，$M \le 100$。 **【题目来源】** NOIP 2005 普及组第三题 **【出题人】** [TIT_0](https://www.luogu.com.cn/user/257340)