分数: 400 点
问题陈述
有 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 每个输入的测试用例。
约束
- 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.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
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
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 和 3 给出的总重量为 10 和总价值 5.
而且,不可能达到总价值 6 或更多,同时满足条件。