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.