题目描述

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

输入格式

第 1 行：两个整数 $n$ (物品数量， $n≤3500$)和 $m$ (背包载重, $m≤12880$)。 第 2..n+1 行，每行二个整数 $w[i]$，$v[i]$，表示每个物品的重量和价值。

输出格式

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

4 6
1 4
2 6
3 12
2 7

23