AT_arc223_a [ARC223A] Unusual-Constraint Knapsack

There are $ N $ items $ 1, 2, \dots, N $ . Item $ i $ has weight $ w_i $ and value $ v_i $ . For $ i = 2, 3, \dots, N $ , the following holds: - $ \sum_{j=1}^{i-1}{w_j} < w_i $ Choose some (possibly zero) items such that the total weight is at most $ W $ . Find the maximum possible total value of the chosen items. Solve $ T $ test cases per input.

The input is given from Standard Input in the following format: > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ Each test case $ \mathrm{case}_t $ is given in the following format: > $ N $ $ W $ $ w_1 $ $ v_1 $ $ w_2 $ $ v_2 $ $ \vdots $ $ w_N $ $ v_N $

Output the answers over a total of $ T $ lines. The $ t $ -th line should contain the answer for the $ t $ -th test case.

### Sample Explanation 1 For the first test case, choosing items $ 1 $ and $ 3 $ gives a total weight of $ 10 $ and a total value of $ 5 $ . Moreover, it is impossible to achieve a total value of $ 6 $ or more while satisfying the condition. ### Constraints - $ 1 \leq T \leq 2 \times 10^5 $ - $ 1 \leq N \leq 60 $ - $ 1 \leq w_i \leq W \leq 10^{18} $ - $ \sum_{j=1}^{i-1}{w_j} < w_i \; (2 \leq i \leq N) $ - $ 1 \leq v_i \leq 10^{16} $ - The sum of $ N $ over all test cases is at most $ 2 \times 10^5 $ . - All input values are integers.