01 背包

题目描述

有 $n$ 件物品，第 $i$ 件物品的重量为 $w_i$，价值为 $v_i$。背包的容量为 $W$，每件物品最多选择一次。

要求选出的物品总重量恰好等于 $W$，求能获得的最大总价值。如果无法恰好装满背包，输出 -1。

输入格式

第一行两个整数 $n$ 和 $W$。

接下来 $n$ 行，每行两个整数 $w_i$ 和 $v_i$。

输出格式

一行一个整数，表示恰好装满背包时的最大总价值；如果无法恰好装满，输出 -1。

样例

4 5
1 2
2 4
3 4
4 5

8

2 5
4 100
3 99

-1

数据范围

$1 \le n \le 100$，$1 \le W \le 10^5$，$1 \le w_i \le W$，$0 \le v_i \le 10^9$。