AT_arc201_b [ARC201B] Binary Knapsack

$ 1,2,\dots,N $ の番号がついた $ N $ 個の品物があります。 品物 $ i $ の重みは $ 2^{X_i} $ で価値は $ Y_i $ です。 重みの和が $ W $ 以下になるように品物を $ 0 $ 個以上選ぶとき、価値の和としてありうる最大値を求めて下さい。 $ T $ 個のテストケースが与えられるので、それぞれについて答えを求めて下さい。

入力は以下の形式で標準入力から与えられる。 > $ 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 $ 番目のテストケースについて、価値の和としてありうる最大値を出力せよ。

### Sample Explanation 1 $ 1 $ つ目のテストケースについて、各品物の重みと価値の組はそれぞれ $ (1,3),(8,2),(16,5),(8,4) $ です。 品物 $ 1,4 $ を選ぶと、重みの和は $ 1+8=9 (\le 16) $ 、価値の和は $ 3+4=7 $ となります。 $ 2 $ つ目のテストケースについて、品物を選ぶ個数は $ 0 $ でも良い点に注意して下さい。 ### 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 $ - 全てのテストケースにおける $ N $ の総和は $ 2 \times 10^5 $ 以下 - 入力される値は全て整数