A. 01背包

题目描述

现有一个承重为 $M$ 的背包和 $N$ 件物品，每件物品有两个属性：重量和价值。请问这个背包最多能装价值为多少的物品？

输入格式

第一行两个整数 $M$ 和 $N$。 接下来 $N$ 行，每行两个整数 $w_i$ 和 $v_i$，表示第 $i$ 件物品的重量与价值。

输出格式

输出背包最多能装的物品价值。

样例

输入

6 3
3 5
2 4
4 2

输出

9

数据范围与提示

• 对于 $90\%$ 的数据：$1 \le N \le 100$，$1 \le M \le 10000$。
• 对于 $100\%$ 的数据：$1 \le N \le 1000$，$1 \le M \le 20000$。
• 每件物品的重量和价值范围：$1 \le w_i, v_i \le 1500$。