恰好装满的最大价值

难度：T2

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

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

题目描述

有 $n$ 件物品，体积为 $w_i$、价值为 $v_i$。每件至多选一次，要求总体积恰好为 $W$，求最大总价值。无法恰好凑出时输出 -1。$W=0$ 时空选择合法，价值为 $0$。不同编号的物品即使属性相同，仍各有一件。

输入格式

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

输出格式

一行一个整数，表示恰好装满时的最大总价值；无合法方案则输出 -1。

样例输入

2 5
2 0
3 7

样例输出

7

样例解释

两件体积合计 $5$，价值 $0+7=7$；零价值物品仍可以帮助装满。

数据范围

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