Problem Statement

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.

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.

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

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