AT_arc223_a.Unusual-Constraint Knapsack

There are $N$ items $1, 2, \dots, N$.
Item $i$ has weight $w_i$ and value $v_i$.
For $i = 2, 3, \dots, N$, the following holds:

• $\sum_{j=1}^{i-1}{w_j} < w_i$

Choose some (possibly zero) items such that the total weight is at most $W$.
Find the maximum possible total value of the chosen items.
Solve $T$ test cases per input.

共有 $N$ 个物品，编号为 $1, 2, \dots, N$。
物品 $i$ 的重量为 $w_i$，价值为 $v_i$。
对 $i = 2, 3, \dots, N$，满足以下条件：

• $\sum_{j=1}^{i-1}{w_j} < w_i$

从中选择若干个（可能为零个）物品，使得所选物品的总重量不超过 $W$。
求所选物品的最大可能总价值。
每组输入包含 $T$ 个测试用例。

The input is given from Standard Input in the following format:

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

Each test case $\mathrm{case}_t$ is given in the following format:

$N$ $W$
$w_1$ $v_1$
$w_2$ $v_2$
$\vdots$
$w_N$ $v_N$

输入从标准输入中按以下格式给出：

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

每个测试用例 $\mathrm{case}_t$ 按以下格式给出：

$N$ $W$
$w_1$ $v_1$
$w_2$ $v_2$
$\vdots$
$w_N$ $v_N$

Output the answers over a total of $T$ lines. The $t$-th line should contain the answer for the $t$-th test case.

在总共 $T$ 行上输出答案。第 $t$ 行应包含第 $t$ 个测试用例的答案。

Sample 1 Explanation:
For the first test case, choosing items $1$ and $3$ gives a total weight of $10$ and a total value of $5$.
Moreover, it is impossible to achieve a total value of $6$ or more while satisfying the condition.

Constraints

• $1 \leq T \leq 2 \times 10^5$
• $1 \leq N \leq 60$
• $1 \leq w_i \leq W \leq 10^{18}$
• $\sum_{j=1}^{i-1}{w_j} < w_i \; (2 \leq i \leq N)$
• $1 \leq v_i \leq 10^{16}$
• The sum of $N$ over all test cases is at most $2 \times 10^5$.
• All input values are integers.

样例 1 解释：
对于第一个测试用例，选择物品 $1$ 和 $3$ 可得到总重量为 $10$、总价值为 $5$。
此外，在满足约束条件的前提下，无法达到总价值 $6$ 或更高。

约束条件

• $1 \leq T \leq 2 \times 10^5$
• $1 \leq N \leq 60$
• $1 \leq w_i \leq W \leq 10^{18}$
• $\sum_{j=1}^{i-1}{w_j} < w_i \; (2 \leq i \leq N)$
• $1 \leq v_i \leq 10^{16}$
• 所有测试用例的 $N$ 之和不超过 $2 \times 10^5$。
• 所有输入值均为整数。