← 返回题目列表

AtCoder · arc201_b

B. 二进制背包

中文机器翻译题面 查看原题

分数: 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 项目。