题目描述

有一个背包，最大承重为 $maxw$。同时有 $n$ 件物品，每件物品都有一个重量 $w_i$ 和一个价值 $p_i$。

请从这 $n$ 件物品中选择若干件装入背包，使得装入物品的总重量不超过 $maxw$，并且总价值最大。

输入格式

第一行输入两个整数 $maxw,n$，分别表示背包最大承重和物品数量。

接下来 $n$ 行，每行两个整数 $w_i,p_i$，分别表示一件物品的重量和价值。

输出格式

输出一个整数，表示背包内物品的最大总价值。

样例

10 3
4 5
5 6
6 7

12

样例解释

选择第 $1$ 件和第 $3$ 件物品，总重量为 $4+6=10$，总价值为 $5+7=12$，可以获得最大价值 $12$。

数据范围

$0 \le maxw \le 20000$，$0 \le n \le 100$，$w_i,p_i$ 均为正整数。

来源

动态规划 / 背包问题