分数: 500 点
问题陈述
有 N 项目编号 1,2,\dots,N。 项目 i 有重量 2^{X_i} 和值 Y_i.
选择时 0 或更多物品,其重量总和最多为 W,找到最大可能的值之和。
T 给出了测试用例,因此请找到每个测试用例的答案。
约束
- 1 \le T \le 10^5
- 1 \le N \le 2 \times 10^5
- 1 \le W \le 10^{18}
- 0 \le X_i \lt 60
- 1 \le Y_i \le 10^9
- 总和 N 所有测试用例最多 2 \times 10^5.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
每个测试用例均按以下格式给出:
N W X_1 Y_1 X_2 Y_2 \vdots X_N Y_N
输出
输出 T 行。
的 树的 i- 第行应包含最大可能的值之和 i- 第一个测试用例。
示例输入 1
3 4 16 0 3 3 2 4 5 3 4 1 576460752303423487 59 1000000000 15 23752394551518 42 457687868 42 527769950 41 336200204 42 555090674 32 452384 42 697175056 38 62269946 39 24293218 40 214670437 37 6306990 39 103832403 41 205334902 37 20326312 35 4723060 42 176783630
示例输出 1
7 0 3102936938
对于第一个测试用例,物品的重量和价值对 1,2,3,4 是 分别为 (1,3),(8,2),(16,5),(8,4)。
如果我们选择项目 1 和 4,权重之和为 1+8=9 (\le 16) 值的总和是 3+4=7.
对于第二个测试用例,注意是允许选择 0 项目。