AT_arc201_b [ARC201B] Binary Knapsack

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.

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 $ T $ lines. The $ i $ -th line should contain the maximum possible sum of values for the $ i $ -th test case.

### Sample Explanation 1 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. ### 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.