背包中的最大价值

难度：T2

【知识点：零一背包、状态初始化】

前置知识：数组、循环、二维状态到一维滚动。

题目描述

有 $n$ 件按编号区分的物品，第 $i$ 件体积 $w_i$、价值 $v_i$。背包容量为 $W$。每件至多选一次，总体积不得超过 $W$，求最大总价值。可以一件都不选。不同编号的物品即使属性相同，仍各有一件。

输入格式

第一行两个整数 $n,W$。接下来 $n$ 行，每行两个整数 $w_i,v_i$。

输出格式

一行一个整数，表示不超过容量时的最大总价值。

样例输入

3 5
2 3
3 4
4 5

样例输出

7

样例解释

选择前两件，总体积 $2+3=5$，价值 $3+4=7$。

数据范围

$1\le n\le100$，$0\le W\le2000$，$1\le w_i\le2000$。 $0\le v_i\le10^9$。