题目描述

小航跟着向导走进一座遍地晶石的山谷。谷里散落着若干株晶石，挖走每一株都要花掉一些时间，而每株晶石也对应着各自的价值。向导只留给他一段有限的时间，时间一到就必须离开山谷。小航想知道，怎样安排挖掘顺序之前的取舍，才能让带走的晶石总价值最高。

如果你是和小航同行的参谋，你能算出这个最大总价值吗？

输入格式

第一行有 $2$ 个整数 $T$（$1 \le T \le 1000$）和 $M$（$1 \le M \le 100$），用一个空格隔开，$T$ 代表总共能够用来采集的时间，$M$ 代表山谷里晶石的数目。

接下来的 $M$ 行每行包括两个在 $1$ 到 $100$ 之间（包括 $1$ 和 $100$）的整数，分别表示采集某株晶石的时间和这株晶石的价值。

输出格式

输出在规定的时间内可以采集到的晶石的最大总价值。

样例

70 3
71 100
69 1
1 2

3

提示

【数据范围】

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