题目描述

淘金客在山洞里发现了大量的珠宝，虽然淘金客很想把所有的财宝都带回去，但是背包容量有限，您是一个小天才，请帮淘金客算出如何带出价值最大的方案。每件财宝都要占据相应的空间，淘金客也知道这件财宝的价值（财宝不可以切割，放在背包的财宝间隙忽略不计）。

输入格式

第一行两个整数v,n;分别代表背包容量，财宝的数量。

接下来n行数字，每行两个数字a,b;分别代表财宝占据的空间和价值。

输出格式

输出背包客能带最大的财宝总价值。

70 3 
90 10000 
20 500 
30 1000

1500

数据规模与约定

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