题目描述

阿里巴巴无意中发现了四十大盗的宝库。他打开宝库，发现里面有很多宝物。但是，阿里巴巴的背包只能装一定重量的宝物。

已知 $n$ 个物品的重量与价值，背包可容纳的最大重量为 $m$。

他希望能够带走价值最高的宝物，你能帮助阿里巴巴选择应该带走哪些宝物吗？

输入格式

第一行包含两个整数 $m$ 和 $n$，分别表示背包的最大承重和宝物的数量。

接下来 $n$ 行每行两个整数，$w_i$ 和 $v_i$，分别表示第 $i(1≤i≤n)$ 件宝物的重量和价值。

输出格式

在不超过背包承重的情况下，阿里巴巴能够带走的宝物的最大总价值。

4 3
1 5
2 7
3 10

15

数据规模与约定

数据保证 $1≤m≤300,1≤n≤30$。