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\)