恰好装满的 01 背包

题目描述

你有一个容量为 $V$ 的背包，以及 $n$ 件物品。第 $i$ 件物品的体积为 $v_i$，价值为 $w_i$。

每件物品最多只能选择一次，物品不能拆分。即使两件物品的体积和价值都相同，它们仍然是两件不同的物品，可以分别选择。

你需要选择若干件物品，使它们的总体积恰好等于 $V$。在所有满足条件的选择方案中，求最大总价值。

如果无法恰好装满背包，输出 -1。

输入格式

第一行包含两个整数 $n,V$，分别表示物品数量和背包容量。

接下来 $n$ 行，第 $i$ 行包含两个整数 $v_i,w_i$，分别表示第 $i$ 件物品的体积和价值。

输出格式

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

样例 1

输入

4 5
2 3
3 4
5 6
1 1

输出

7

说明

选择第 1、2 件物品，总体积为 $2+3=5$，总价值为 $3+4=7$。选择第 3 件物品也能恰好装满，但总价值只有 $6$。

样例 2

输入

1 3
2 3

输出

-1

说明

唯一一件物品的体积为 $2$，无法恰好装满容量为 $3$ 的背包。

样例 3

输入

2 5
2 0
3 0

输出

0

说明

选择两件物品可以恰好装满，总价值为 $0$。价值为 $0$ 的方案也是合法方案。

数据范围

对于所有测试数据，保证：

• $1\le n\le5000$。
• $0\le V\le5000$。
• $1\le v_i\le5000$。
• $0\le w_i\le10^6$。
• 所有输入均为整数。

当 $V=0$ 时，可以不选择任何物品，答案为 $0$。

答案可能超过 32 位有符号整数的范围，请使用 64 位整数保存总价值。