终于到了午餐时间!
$$$n$$$ 学生们在厨师的帐篷前排起了长队买粥。厨师将提供粥 $$$D$$$ 分钟。站在队列中第 $$$i$$$ 位置的小学生的优先级为 $$$k_i$$$,并在 $$$s_i$$$ 分钟内吃完一份粥。
在休息的每一分钟开始时,厨师都会为队列中的第一个学童提供一份粥,然后该学童去吃自己的那一份。如果第 $$$i$$$ 学童在第 $$$x$$$ 分钟开始时得到一份食物,那么他们将在第 $$$(x + s_i)$$$ 分钟结束时返回队列。
当第 $$$i$$$ 个学童返回队列时,队列末尾优先级严格低于第 $$$i$$$ 个学童的学童必须让其通过。因此,他们将站在队列中优先级不低于自己的最后一个学生的后面。也就是说,在最后一个学生 $$$j$$$ 后面,$$$k_j \ge k_i$$$。如果队列中没有这样的学生,则第 $$$i$$$ 个学生将站在队列的前面。
如果多个学童同时返回,他们将按照 $$$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$$$ 分钟内不会发生这种情况。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) - 测试用例的数量。接下来是测试用例的描述。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$D$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le D \le 3\cdot 10^5$$$) - 分别是队列中学童的数量和休息时间。
接下来的 $$$n$$$ 行包含两个整数 $$$k_i$$$ 和 $$$s_i$$$ ($$$1 \le k_i, s_i, \le 10^9$$$) - 各个学童吃一份粥的优先级和时间。学生按照他们在队列中站立的顺序(从最前面到最后)排列。
保证所有输入数据集的$$$n$$$值之和不超过$$$2\cdot 10^5$$$。同样,保证所有输入数据集的$$$D$$$的值之和不超过$$$3\cdot 10^5$$$。
输出
对于每个测试用例,输出每个学童至少收到一次粥的最小分钟数。如果在休息时间内没有发生这种情况,则输出$$$-1$$$。
示例
输入 #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
输出 #1
3 -1 12 6 6 1 6