DP603 旅行装备选择

难度梯度：T3｜训练重点：01 背包倒序

题目描述

背包容量为 W，有 N 件装备，第 i 件体积 v_i、价值 c_i，每件至多选一次。求总容量不超过 W 时最大总价值。

每件装备只有一件；允许不选择任何装备，此时体积与价值均为 0。容量可以剩余。

输入格式

第一行 N W；接下来 N 行 v_i c_i。

输出格式

输出最大价值。

样例输入

3 5
2 4
3 5
4 7

样例输出

9

样例说明

选体积 2 和 3 两件。

数据范围

1≤N≤100；1≤W≤10^5；1≤v_i≤W；1≤c_i≤10^9。

子任务

30 分：N≤20；30 分：W≤1000；40 分：无附加限制。