题目描述

有一个背包能装的重量 $maxw$ (正整数， $0 \le maxw \le 20000$)，同时有 $n$ 件物品($1 \le n \le 100$)，每件物品有一个重量 $w_i$ (正整数)和一个价值 $p_i$ (正整数)。要求从这 $n$ 件物品中任取若干件装入背包内，使背包的物品价值最大。

输入

第 $1$ 行：背包最大载重 $maxw$ ，物品总数 $n$ ；

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

输出

一个数字即背包内物品最大价值；

样例

10 3
4 5
3 4
6 9

14

来源

动态规划 背包问题