随着隔离措施的解除，Jack 的家乡决定举办一场节日庆典。Jack 仍然对接触过多人群保持谨慎，因此他希望通过一种简单的策略来规划他在庆典中的路线，以最大化他的幸福感。

庆典共有 $N$ 个摊位，编号从 $1$ 到 $N$。如果 Jack 进入第 $i$ 个摊位，他会遇到 $p_i$ 个人并获得 $h_i$ 的幸福感。他按顺序从第 $1$ 个摊位走到第 $N$ 个摊位，且不会重复访问任何摊位。在每个摊位，他可以选择进入或直接走过。

题目保证对于所有 $i < N$，$p_i \ge p_{i+1}$，因为较早的摊位往往会吸引更多的人群。

Jack 希望总共遇到的人数不超过 $P$。此外，他只考虑那些幸福感超过某个阈值 $threshold$ 的摊位。该阈值应为一个非负整数。

形式化地，设 $ht$ 为 Jack 的总幸福感，$m$ 为他遇到的人数总和。Jack 将遵循以下策略。

Jack 的策略（伪代码）：

ht = 0 // 最初，总幸福感为 0
m = 0 // 最初，他遇到的人数为 0
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 希望选择一个能使他的总幸福感 $ht$ 最大化的 $threshold$ 值。如果存在多个阈值能达到相同的最大幸福感，他希望选择其中最小的那个阈值。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10^5$) —— 测试用例的数量。

每个测试用例包含： 第一行包含两个整数 $N$ 和 $P$ ($1 \le N \le 2 \cdot 10^5, 1 \le P \le 10^{18}$) —— 摊位数量和 Jack 希望遇到的最大人数。

接下来的 $N$ 行，每行包含两个整数 $h_i$ 和 $p_i$ ($1 \le h_i \le 10^9, 1 \le p_i \le 10^{18}$) —— 在第 $i$ 个摊位获得的幸福感和遇到的人数。

题目保证所有测试用例的 $N$ 之和不超过 $2 \cdot 10^5$。 此外，对于每个测试用例，所有 $p_i$ 之和不超过 $10^{18}$，且对于所有 $j < N$，$p_j \ge p_{j+1}$。

输出格式

对于每个测试用例，输出两个整数 —— Jack 能达到的最大总幸福感，以及达到该总幸福感所需的最小阈值。

样例

输入 1

2
4 15
4 6
1 5
3 3
3 1
4 14
4 6
1 5
3 3
3 1

输出 1

11 0
10 1

说明

在第一个测试用例中，Jack 可以进入每一个摊位而不会超过他希望遇到的最大人数。因此，最优阈值为 $0$。

在第二个测试用例中，如果阈值设为 $0$，Jack 将跳过第 $3$ 个摊位，导致总幸福感为 $8$。如果阈值增加到 $1$，他将因为阈值条件而跳过第 $2$ 个摊位，从而获得 $10$ 的总幸福感，这是可能达到的最大值。阈值 $2$ 也能得到 $10$ 的总幸福感，但它不是最小的。