Bob goes to the fruit shop to buy apples. There are $N$ apples numbered from $1$ to $N$ where the vitamin value of the $i^{th}$ apple is $V_i$ and the price of the $i^{th}$ apple is $P_i$.

He wants to buy apples such that the sum of the price does not exceed $M$. He has one special magic spell. By using it, he can halve the price (floor value) of any apple present in a shop. He can use this spell at most one time.

Your task is to find the maximum vitamin Bob can get.

Input format

• The first line contains an integer $T$ denoting the number of test cases.
• The first line of each test case contains two space-separated integers $N$ and $M$.
• The next $N$ lines contain two space-separated values $V_i$ and $P_i$.

Output format

For each test case, the only line must contain an integer denoting the maximum vitamin Bob can get.

Constraints

$1 \le T \le 10$

$1 \le N \le 1000$

$1 \le M \le 1000$

$1 \le V_i \le 10^5$

$1 \le P_i \le 10^3$