01背包

题目描述

有 $n$ 个物品，编号为 $i$ 的物品的重量为 $w[i]$，价值为 $v[i]$，现在要从这些物品中选一些物品装到一个载重为 $m$ 的背包中，使得背包内物体在总重量不超过 $m$ 的前提下价值尽量大。

输入格式

第 $1$ 行：两个整数 $n$（物品数量，$n \le 3500$）和 $m$（背包载重，$m \le 12880$）。

第 $2 \dots n+1$ 行，每行二个整数 $w[i]$，$v[i]$，表示每个物品的重量和价值。

输出格式

仅一行，一个数，表示最大总价值。

样例输入 #1

4 6
1 4
2 6
3 12
2 7

样例输出 #1

23

数据范围与提示

$n \le 3500$，$m \le 12880$，$1 < w[i]$，$v[i] \le 1000$。

时间限制：1000MS，内存限制：64MB。

知识点与难度

本题涉及的知识点从属于 GESP 6级，难度等级：⭐⭐⭐⭐⭐。

测试点分布