题目描述

有一个背包能装的重量 $C$ ( $0 ≤ C ≤ 30000$ )，同时有 $n$ 件物品 ( $1 ≤ n ≤ 200$ )，每件物品有一个重量 $wi$​ 和一个价值 $vi$​ 。要求从这 $n$ 件物品中任取若干件装入背包内，使背包的物品价值最大。

输入格式

第 1 行：背包最大重量 $C$，物品总数 $n$ ；( $0 ≤ C ≤ 30000$ , $1 ≤ n ≤ 200$ )

第 2 行到第 $n+1$ 行：每个物品的重量和价值；

输出格式

输出背包内物品的最大价值；

样例

6 5
2 3
2 6
4 6
6 5
2 8

17

10 3
4 5
3 4
6 9

14