题目描述

退潮时有不同的贝类，每拾一颗都需要一些时间，每一颗也有它自身的价值。你有一段时间，在这段时间里，你可以拿取到一些贝类。应该可以让拿到的贝类的总价值最大。

输入格式

第一行有 $2$ 个整数 $T$（$1 \le T \le 1000$）和 $M$（$1 \le M \le 100$），用一个空格隔开，$T$ 代表总共能够用来拾贝壳的时间，$M$ 代表海滩上的贝壳的数目。

接下来的 $M$ 行每行包括两个在 $1$ 到 $100$ 之间（包括 $1$ 和 $100$）的整数，分别表示拾起贝壳的时间和这颗贝壳的价值。

输出格式

输出在规定的时间内可以拾起贝壳最大总价值。

样例 #1

样例输入 #1

70 3
71 100
69 1
1 2

样例输出 #1

3

提示

【数据范围】

• 对于 $30\%$ 的数据，$M \le 10$；
• 对于全部的数据，$M \le 100$。