311182: CF1945G. Cook and Porridge

G. Cook and Porridgetime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Finally, lunchtime!

$n$ schoolchildren have lined up in a long queue at the cook's tent for porridge. The cook will be serving porridge for $D$ minutes. The schoolchild standing in the $i$-th position in the queue has a priority of $k_i$ and eats one portion of porridge in $s_i$ minutes.

At the beginning of each minute of the break, the cook serves the first schoolchild in the queue one portion of porridge, after which the schoolchild goes to eat their portion. If the $i$-th schoolchild is served a portion at the beginning of the $x$-th minute, then they will return to the queue at the end of the $(x + s_i)$-th minute.

When the $i$-th schoolchild returns to the queue, the schoolchildren at the end of the queue whose priority is strictly lower than that of the $i$-th schoolchild must let them pass. Thus, they will stand in the queue behind the last schoolchild whose priority is not lower than their own. That is, behind the last schoolchild $j$ with $k_j \ge k_i$. If there is no such schoolchild in the queue, the $i$-th schoolchild will stand at the front of the queue.

If several schoolchildren return at the same time, they will return to the queue in ascending order of their $s_i$.

For example, if $n = 3$, $D = 3$, $k = [2, 3, 2]$, and $s = [2, 1, 3]$, the serving will occur as follows:

• At the beginning of minute $1$, the students in the queue are $[1, 2, 3]$, and student $1$ is served porridge;
• at the beginning of minute $2$, the students in the queue are $[2, 3]$, and student $2$ is served porridge;
• at the beginning of minute $3$, the student in the queue is $[3]$, and student $3$ is served porridge;
• at the end of minute $3$, student $2$ returns to the queue, and the queue becomes $[2]$;
• at the end of minute $3$, student $1$ returns to the queue, and the queue becomes $[2, 1]$, as his priority is lower.

Determine the minimum number of minutes after the start of the break that each schoolchild will receive porridge at least once, or report that this will not happen within $D$ minutes.

Input

Each test consists of several test cases. The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases. This is followed by a description of the test cases.

The first line of each test case contains two integers $n$ and $D$ ($1 \le n \le 2 \cdot 10^5$, $1 \le D \le 3\cdot 10^5$) — the number of schoolchildren in the queue and the break time, respectively.

The next $n$ lines contain two integers $k_i$ and $s_i$ ($1 \le k_i, s_i, \le 10^9$) — the priority and the time to eat one portion of porridge for the respective schoolchild. The schoolchildren are given in the order they stand in the queue (from the front to the end).

It is guaranteed that the sum of the values of $n$ for all input data sets does not exceed $2\cdot 10^5$. Similarly, it is guaranteed that the sum of the values of $D$ for all input data sets does not exceed $3\cdot 10^5$.

Output

For each test case, output the minimum number of minutes after which each schoolchild will receive porridge at least once. If this does not happen within the break time, output $-1$.

ExampleInput

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

Output

3
-1
12
6
6
1
6

题目大意：
有n个学生站在厨师的大篷车前排队等着吃粥。厨师将在D分钟内供应粥。队列中第i个位置的学生有一个优先级k_i，吃一份粥需要s_i分钟。

每分钟开始时，厨师会为队列中的第一个学生提供一份粥，然后这个学生去吃他们的那份。如果第i个学生在第x分钟的开始时被提供了粥，那么他们将在第(x + s_i)分钟的末尾回到队列中。

当第i个学生回到队列时，队列末尾优先级严格低于第i个学生的学生必须让他们通过。也就是说，他们会站在队列中最后一个优先级不低于他们自己的学生后面。如果没有这样的学生，第i个学生将站在队列的最前面。

如果有几个学生同时回来，他们会按照s_i的升序回到队列中。

输入数据格式：
输入包含多个测试用例。第一行包含一个整数t（1≤t≤1000）——测试用例的数量。接下来是测试用例的描述。

每个测试用例的第一行包含两个整数n和D（1≤n≤2×10^5，1≤D≤3×10^5）——队列中的学生数量和休息时间。

接下来n行包含两个整数k_i和s_i（1≤k_i,s_i≤10^9）——相应学生的优先级和吃一份粥的时间。学生的顺序按照他们在队列中的站立顺序给出（从前到后）。

保证所有输入数据集中n的值的总和不超过2×10^5。同样，保证所有输入数据集中D的值的总和不超过3×10^5。

输出数据格式：
对于每个测试用例，输出使得每个学生至少吃一次粥所需的最小分钟数。如果这在休息时间内不会发生，输出-1。题目大意： 有n个学生站在厨师的大篷车前排队等着吃粥。厨师将在D分钟内供应粥。队列中第i个位置的学生有一个优先级k_i，吃一份粥需要s_i分钟。 每分钟开始时，厨师会为队列中的第一个学生提供一份粥，然后这个学生去吃他们的那份。如果第i个学生在第x分钟的开始时被提供了粥，那么他们将在第(x + s_i)分钟的末尾回到队列中。 当第i个学生回到队列时，队列末尾优先级严格低于第i个学生的学生必须让他们通过。也就是说，他们会站在队列中最后一个优先级不低于他们自己的学生后面。如果没有这样的学生，第i个学生将站在队列的最前面。 如果有几个学生同时回来，他们会按照s_i的升序回到队列中。 输入数据格式： 输入包含多个测试用例。第一行包含一个整数t（1≤t≤1000）——测试用例的数量。接下来是测试用例的描述。 每个测试用例的第一行包含两个整数n和D（1≤n≤2×10^5，1≤D≤3×10^5）——队列中的学生数量和休息时间。 接下来n行包含两个整数k_i和s_i（1≤k_i,s_i≤10^9）——相应学生的优先级和吃一份粥的时间。学生的顺序按照他们在队列中的站立顺序给出（从前到后）。 保证所有输入数据集中n的值的总和不超过2×10^5。同样，保证所有输入数据集中D的值的总和不超过3×10^5。 输出数据格式： 对于每个测试用例，输出使得每个学生至少吃一次粥所需的最小分钟数。如果这在休息时间内不会发生，输出-1。