特殊约束背包

时间限制：2s
空间限制：1024MB

题目描述

有 $N$ 个物品，编号为 $1,2,\ldots,N$。物品 $i$ 的重量为 $w_i$，价值为 $v_i$。对于每个 $2\le i\le N$，均满足

请选出若干个物品（也可以一个都不选），使总重量不超过 $W$，并求所选物品总价值的最大值。

你需要处理 $T$ 组测试数据。

输入格式

第一行输入整数 $T$。

随后依次输入每组测试数据。每组数据第一行输入两个整数 $N,W$；接下来 $N$ 行，第 $i$ 行输入两个整数 $w_i,v_i$。

输出格式

对每组测试数据输出一行一个整数，表示最大总价值。

样例输入 1

3
3 10
1 2
3 1
9 3
3 20
1 2
3 1
9 3
4 15
1 1
3 2
5 3
10 4

样例输出 1

5
6
7

数据范围

对于所有数据：

• $1\le T\le2\times10^5$；
• $1\le N\le60$；
• $1\le w_i\le W\le10^{18}$；
• $\sum_{j=1}^{i-1}w_j<w_i$ 对所有 $2\le i\le N$ 成立；
• $1\le v_i\le10^{16}$；
• 单个测试点内所有测试数据的 $N$ 之和不超过 $2\times10^5$。