题目描述

从前有个山洞里，洞有 $n$ 个宝石，第 $i$ 个宝石拿到市场能卖 $m_i$ 块钱，但是要拿走第 $i$ 颗宝石需要花费 $t_i$ 秒的时间。

山洞 $v$ 秒之后就会倒塌。

求在能活着离开山洞的前提下，获取的宝石总价值最大。

输入格式

第一行有两个整数 $v$ 和 $n$。 接下来的 $n$ 行每行两个整数 $t_i$ 和 $m_i$。

输出格式

输出一行，一个整数，即最大总价值。

70 3
71 100
69 1
1 2

3

16 5
5 4
8 9
7 5
3 4
6 9

18

数据规模与约定

对于 $30\%$ 的数据，$n\le 10$；

对于 $100\%$ 的数据，$n\le 100$，$1\le v\le 1000$，$0\le t_i,m_i\le 100$。

题目来源

来源于 NOIP2005 普及组第三题《采药》