CF1945G Cook and Porridge

终于到午饭时间了！ 有 $n$ 名学生在食堂的厨师帐篷前排成一条长队等待喝粥。厨师将在 $D$ 分钟内为大家分发粥。队列中第 $i$ 位学生有优先级 $k_i$，且吃完一份粥需要 $s_i$ 分钟。 在每一分钟的开始，厨师会为队首的学生分发一份粥，然后该学生去吃粥。如果第 $i$ 位学生在第 $x$ 分钟开始时拿到粥，那么他会在第 $(x + s_i)$ 分钟结束时返回队列。 当第 $i$ 位学生返回队列时，队尾所有优先级严格低于 $k_i$ 的学生都必须让他插队。因此，他会站在队列中最后一个优先级不低于他自己的学生后面。也就是说，排在最后一个 $k_j \ge k_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$ 分钟内无法做到，请输出 $-1$。

每组测试数据包含若干测试用例。第一行包含一个整数 $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$），分别表示第 $i$ 位学生的优先级和吃完一份粥所需的时间。学生按队列顺序给出（从队首到队尾）。 保证所有输入数据中 $n$ 的总和不超过 $2\cdot 10^5$，$D$ 的总和不超过 $3\cdot 10^5$。

对于每个测试用例，输出一个整数，表示每位学生至少能喝到一次粥所需的最少分钟数。如果在午休时间内无法做到，输出 $-1$。

由 ChatGPT 4.1 翻译