G. 厨师与粥

单个测试点时间限制：$2$ 秒 单个测试点内存限制：$256$ 兆字节

终于到午饭时间了！

有 $n$ 名小学生在厨师的帐篷前排成长队等候喝粥。厨师会在接下来的 $D$ 分钟内分发粥。 队列中第 $i$ 位学生的优先级为 $k_i$，吃掉一份粥需要 $s_i$ 分钟。

在休息时间的每一分钟开始时，厨师会给队列的第一位学生盛一份粥，之后这名学生就去吃粥。 如果第 $i$ 名学生在第 $x$ 分钟开始时被分到粥，那么他会在第 $(x+s_i)$ 分钟结束时回到队列。

当第 $i$ 名学生回到队列时，队列末尾所有优先级严格低于 $k_i$ 的学生都必须给他让路。 也就是说，他会插到队列中最后一个优先级不低于他的学生后面，即最后一个满足 $k_j\ge k_i$ 的学生 $j$ 的后方。 如果队列中不存在这样的学生，这名学生就会站到队首。

如果多名学生同时返回，他们会按照 $s_i$ 升序依次回到队列。

例如，当 $n=3$，$D=3$，$k=[2,3,2]$，$s=[2,1,3]$ 时，分发过程如下：

• 第 $1$ 分钟开始，队列为 $[1,2,3]$，学生 $1$ 分到粥；
• 第 $2$ 分钟开始，队列为 $[2,3]$，学生 $2$ 分到粥；
• 第 $3$ 分钟开始，队列为 $[3]$，学生 $3$ 分到粥；
• 第 $3$ 分钟结束，学生 $2$ 回到队列，队列变为 $[2]$；
• 第 $3$ 分钟结束，学生 $1$ 回到队列，由于优先级更低，队列变为 $[2,1]$。

你需要求出：从休息开始，最少经过多少分钟，每名学生都至少分到过一次粥。 如果在 $D$ 分钟内无法做到，输出 $-1$。

输入格式

输入包含多组测试数据。 第一行一个整数 $t$（$1\le t\le 1000$），表示测试用例数量。

每组测试用例格式如下： 第一行两个整数 $n$ 和 $D$（$1\le n\le 2\times10^5$，$1\le D\le 3\times10^5$），分别表示队列中学生人数和总时长。

接下来 $n$ 行，每行两个整数 $k_i$ 和 $s_i$（$1\le k_i,s_i\le 10^9$），分别表示第 $i$ 名学生的优先级和吃粥时间。 学生按初始队列顺序给出（从队首到队尾）。

保证所有测试用例的 $n$ 之和不超过 $2\times10^5$，所有测试用例的 $D$ 之和不超过 $3\times10^5$。

输出格式

对于每组测试用例，输出一个整数，表示所有学生都至少分到一次粥的最早时间。 如果在 $D$ 分钟内无法完成，输出 $-1$。

样例输入

7
3 3
2 2
3 1
2 3
5 10
10 3
7 1
11 3
5 1
6 1
5 20
4 2
7 2
8 5
1 5
3 1
5 17
1 3
8 2
8 3
2 2
1 1
5 14
8 2
4 2
1 3
8 3
6 4
1 11
4 5
5 14
8 2
4 2
1 3
8 3
6 4

样例输出

3
-1
12
6
6
1
6