F. Festival Stroll
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

With the quarantine measures lifted, Jack's hometown decides to hold a festival. Jack is still cautious about meeting too many people, so he wants to plan his route through the festival to maximize his happiness using a simple strategy.

The festival has $$$N$$$ stalls, numbered from $$$1$$$ to $$$N$$$. If Jack enters the $$$i$$$-th stall, he meets $$$p_i$$$ people and gains happiness $$$h_i$$$. He walks from stall $$$1$$$ to stall $$$N$$$ in order and does not revisit any stall. At each stall, he can either enter it or walk past it.

It is guaranteed that $$$p_i \ge p_{i+1}$$$ for all $$$i \lt N$$$, since earlier stalls tend to draw larger crowds.

Jack wants to meet at most $$$P$$$ people in total. He also considers only stalls whose happiness exceeds a certain threshold value $$$threshold$$$. The $$$threshold$$$ should be a non-negative integer.

Formally, let $$$ht$$$ be Jack's total happiness and $$$m$$$ be the number of people he has met. Jack will follow the following strategy.

Jack's strategy (pseudo-code): 


ht = 0 // initially, the total happiness is zero
m = 0 // initially, he meets zero person
for i = 1 to N:
    if h[i] > threshold and m + p[i] <= P:
        enter stall i
        ht = ht + h[i]
        m = m + p[i]
    else:
        skip stall i

Jack wants to choose the value of $$$threshold$$$ that maximizes his total happiness $$$ht$$$. If multiple thresholds achieve the same maximum happiness, he wants the minimum such threshold.

Input

The first line contains a single integer $$$T$$$ ($$$1 \le T \le 10^5$$$) — the number of test cases.

Each test case consists of:

The first line contains two integers $$$N$$$ and $$$P$$$ ($$$1 \le N \le 2 \cdot 10^5$$$, $$$1 \le P \le 10^{18}$$$) — the number of stalls and the maximum number of people Jack wants to meet.

Each of the next $$$N$$$ lines contains two integers $$$h_i$$$ and $$$p_i$$$ ($$$1 \le h_i \le 10^9$$$, $$$1 \le p_i \le 10^{18}$$$) — the happiness gained and the number of people met at the $$$i$$$-th stall.

It is guaranteed that the sum of $$$N$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Additionally, for each test case, the sum of all $$$p_i$$$ does not exceed $$$10^{18}$$$ and $$$p_j \ge p_{j+1}$$$ for all $$$j \lt N$$$.

Output

For each test case, print two integers — the maximum total happiness Jack can achieve and the minimum threshold to achieve the total happiness.

Example
Input
2
4 15
4 6
1 5
3 3
3 1
4 14
4 6
1 5
3 3
3 1
Output
11 0
10 1
Note

In the first test case, Jack can enter every stall without exceeding the maximum number of people he wants to meet. Therefore, the optimal threshold is $$$0$$$.

In the second test case, if the threshold is set to $$$0$$$, Jack will skip stall $$$3$$$, resulting in a total happiness of $$$8$$$. If the threshold is increased to $$$1$$$, he will instead skip stall $$$2$$$ due to the threshold condition, resulting in a total happiness of $$$10$$$, which is the maximum possible. Threshold value $$$2$$$ also resulted in total happiness of $$$10$$$, but it is not minimal.