该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

双色信标

题目描述

在一个周长为 $L$ 的环形轨道上，分布着 $N$ 个基站。这些基站按顺时针方向依次编号为 $1$ 到 $N$。第 $i$ 个基站由两个参数描述：

• 坐标 $x_i$ ($0 \le x_i < L$)：表示该基站沿顺时针方向相对于零点的距离。
• 颜色 $c_i$ ($c_i \in \{0, 1\}$)：表示该基站的信号类型。

为了构建防御网络，你需要从这 $N$ 个基站中恰好选出 $K$ 个作为“信标”。为了保证网络的稳定性，选出的信标必须满足以下两个条件：

1. 颜色交替规则：

   将选出的 $K$ 个信标按坐标顺时针排列，记为 $p_1, p_2, \dots, p_K$。它们的颜色必须交替出现。也就是说，对于任意 $1 \le j < K$，都有 $c_{p_j} \neq c_{p_{j+1}}$。

   此外，由于是环形结构，最后一个信标 $p_K$ 与第一个信标 $p_1$ 也视为相邻，因此也必须满足 $c_{p_K} \neq c_{p_1}$。

   (注：题目保证 $K$ 为偶数。)

2. 安全距离规则：

   任意两个相邻信标（沿顺时针方向）之间的距离必须至少为 $D$。具体来说：

   • 对于 $1 \le j < K$，需满足 $x_{p_{j+1}} - x_{p_j} \ge D$。
   • 对于首尾，需满足 $L - (x_{p_K} - x_{p_1}) \ge D$（即从 $p_K$ 顺时针走到 $p_1$ 跨越边界的距离）。

请你计算并输出能够满足上述所有条件的最大整数 $D$。如果不存在任何一种方案能选出满足条件的 $K$ 个信标，请输出 $-1$。

输入格式

本题仅包含一组测试数据。

第一行包含三个整数 $N, K, L$ ($2 \le N \le 2 \cdot 10^5$, $2 \le K \le N$, $K$ 为偶数, $2 \le L \le 10^9$)，分别表示基站总数、需要选择的信标数量以及环形轨道的周长。

接下来 $N$ 行，每行包含两个整数 $x_i, c_i$ ($0 \le x_i < L, c_i \in \{0, 1\}$)，分别表示第 $i$ 个基站的坐标和颜色。

保证输入的坐标 $x_i$ 是严格递增的（即 $0 \le x_1 < x_2 < \dots < x_N < L$）。

输出格式

输出一个整数，表示最大的安全距离 $D$。如果无解，输出 $-1$。

输入输出样例 #1

输入 #1

6 4 20
0 0
3 1
6 0
9 1
12 0
16 1

输出 #1

3

输入输出样例 #2

输入 #2

4 4 100
0 0
10 0
20 1
30 1

输出 #2

-1

说明/提示

样例 1 解释：

我们可以选择坐标为 $\{0, 3, 6, 9\}$ 的四个基站作为信标。

• 颜色检查：坐标对应的颜色分别为 $0, 1, 0, 1$。顺时针序列为 $0 \to 1 \to 0 \to 1$，且首尾 $1 \to 0$ 也不同，满足交替规则。

• 距离检查：

  • $0 \to 3$：距离 $3$

  • $3 \to 6$：距离 $3$

  • $6 \to 9$：距离 $3$

  • $9 \to 0$（跨越边界）：距离 $20 - (9 - 0) = 11$

    最小间距为 $3$，满足 $D=3$。可以证明没有更大的 $D$ 满足条件。

样例 2 解释：

我们需要选 $4$ 个点，且颜色必须交替。这要求我们选出 $2$ 个颜色为 $0$ 的点和 $2$ 个颜色为 $1$ 的点，并且它们在圆环上的顺序必须是 $0, 1, 0, 1$。

题目给出的点按顺时针顺序颜色为 $0, 0, 1, 1$。无论如何选择，都无法形成交替的序列，因此无解，输出 $-1$。