B - Binary Knapsack Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

1,2,\dots,N の番号がついた N 個の品物があります。 品物 i の重みは 2^{X_i} で価値は Y_i です。

重みの和が W 以下になるように品物を 0 個以上選ぶとき、価値の和としてありうる最大値を求めて下さい。

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 つ目のテストケースについて、各品物の重みと価値の組はそれぞれ (1,3),(8,2),(16,5),(8,4) です。

品物 1,4 を選ぶと、重みの和は 1+8=9 (\le 16)、価値の和は 3+4=7 となります。

2 つ目のテストケースについて、品物を選ぶ個数は 0 でも良い点に注意して下さい。

Score : 500 points

Problem Statement

There are N items numbered 1,2,\dots,N. Item i has weight 2^{X_i} and value Y_i.

When choosing 0 or more items such that the sum of weights is at most W, find the maximum possible sum of values.

T test cases are given, so find the answer for each.

Constraints

  • 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
  • The sum of N over all test cases is at most 2 \times 10^5.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

Each test case is given in the following format:

N W
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N

Output

Output T lines.

The i-th line should contain the maximum possible sum of values for the i-th test case.

Sample Input 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

Sample Output 1

7
0
3102936938

For the first test case, the pairs of weight and value for items 1,2,3,4 are (1,3),(8,2),(16,5),(8,4), respectively.

If we choose items 1 and 4, the sum of weights is 1+8=9 (\le 16) and the sum of values is 3+4=7.

For the second test case, note that it is allowed to choose 0 items.