AT_arc223_a [ARC223A] Unusual-Constraint Knapsack

有 $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$ 组测试用例。

输入从标准输入读入，格式如下： > $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$

输出共 $T$ 行，第 $t$ 行输出第 $t$ 个测试用例的答案。

### 样例解释 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$。 - 所有输入值均为整数。 由 ChatGPT 5 翻译