AT_arc201_b.[ARC201B] Binary Knapsack

提高+/省选-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有 $N$ 个物品，第 $i$ 个物品重量为 $2^{X_i}$ ，价值为 $Y_i$ 。

你可以从中选择任意多个重量之和不超过 $W$ 的物品，求它们价值之和的最大值。

多组数据。

输入格式

多组数据。第一行一个整数 $T(1\le T\le10^5)$ ，表示数据组数。

对于每组数据，第一行两个整数 $N,W(1\le N\le 2\times 10^5,1\le W\le 10^{18})$ 。
接下来 $N$ 行，每行两个整数 $X_i,Y_i(0\le X_i<60,1\le Y_i\le 10^9)$ 。

保证单个测试点内 $\sum N\le 2\times 10^5$ 。

输出格式

对于每组数据，输出一行一个整数表示答案。

输入输出样例

输入#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$ 和物品 $4$ ，重量之和为 $1+8=9\le 16$ ，价值之和为 $3+4=7$ 。

对于第二组数据，注意你可以不选择任何物品。

输入解题思路，AI测评打分。不知道怎么写?

首页