CF2271D Target Infection

给你 $n$ 个两两不相交的感染区间，位于数轴上。第 $i$ 个区间是 $[l_i, r_i]$，表示 $l_i \le x \le r_i$ 的每个整数位置 $x$ 都被感染。所有没有被这些区间覆盖的整数位置都是未感染的。 有 $m$ 个人排成一排。如果第一个人站在位置 $s$，则他们分别站在位置 $s, s+1, \ldots, s+m-1$。如果某个人站的位置被感染，则这个人也被感染。 对于一个整数 $s$，定义 $f(s)$ 表示当第一个人站在位置 $s$ 时，被感染的人的数量。 现给定一个整数 $k$。请你找出任意一个整数 $s$，使得 $f(s) = k$，或者判断不存在这样的 $s$。

每组测试数据包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。接下来是每个测试用例的描述。 每个测试用例的第一行包含三个整数 $n,\ m,\ k$（$1 \le n \le 2 \cdot 10^5$，$1 \le m \le 10^9$，$0 \le k \le m$），分别表示感染区间的数量、人的数量和要求被感染的人数。 接下来的 $n$ 行，每行两个整数 $l_i,\ r_i$（$1 \le l_i \le r_i \le 10^{15}$），表示第 $i$ 个感染区间的端点。保证对每个 $1 \le i < n$ 都有 $r_i + 1 < l_{i+1}$，即区间两两不相交、无连接，并且从左到右依次给出。 保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

对于每个测试用例，如果不存在整数 $s$ 使得 $f(s) = k$，输出 $-1$。 否则，输出一个整数 $s$（$1 \le s \le 10^{18}$），表示一个满足条件的位置。可以证明，如果有解，则必然存在 $1 \le s \le 10^{18}$ 的解。 若有多个解，输出其中任意一个均可。

在第一个样例中，$s = 7$ 是一个可行解。此时人所站位置为 $7, 8, 9, 10, 11$，均被感染，所以 $f(7) = 5$。 在第二个样例中，可以证明不存在满足条件的位置。 在第三个样例中，$s = 2$ 是一种可行方案。此时站在 $2, 3, 4, 5, 6$，其中 $2, 3, 5, 6$ 被感染，$4$ 未被感染，所以 $f(2) = 4$。 由 ChatGPT 5 翻译