P16378 [NordicOI 2026] Alarms 闹钟

翻译来源：loj [#5709. 「NordicOI 2026」Alarms](https://loj.ac/p/5709)。 7s，1024MB。 Subtask 0 为样例。

你的朋友 Emil 收集了大量的闹钟，它们会在不同的时间响起，用来叫醒他并提醒他各种事情。他向你发起挑战，要求你挑选其中的一些闹钟，并对其进行处理。你决定挑选这些闹钟，使得存在一段尽可能长的无干扰时间，这样你就能获得充足的睡眠。 Emil 有 $N$ 个闹钟。挑战的内容是挑选 $K$ 个闹钟，并在 $T$ 秒的时间内观察它们。这 $T$ 秒是指 $t=0$ 到 $t=T$ 之间的连续时间间隔。 Emil 的第 $i$ 个闹钟会在时间点 $t_1, t_2, \dots, t_{m_i}$ 响起，其中 $m_i$ 是正整数。 你的任务是找到一个可能的时间间隔 $(L, R)$，满足 $0 \leq L \leq R \leq T$，使得在这段时间内没有被选中的 $K$ 个闹钟响起。 请注意，该时间间隔是开区间（即由所有满足 $L < t < R$ 的时间 $t$ 组成）。因此，如果闹钟在 $t = L$ 或 $t = R$ 时响起，这是允许的。

第一行包含三个整数 $N, K$ 和 $T$ $(1 \leq K \leq N \leq 3 \cdot 10^5, 1 \leq T \leq 10^9)$，分别表示 Emil 拥有的闹钟总数、你需要挑选的闹钟数量以及挑战持续的时间。 接下来 $N$ 行，每行包含一个正整数 $m_i$，随后是 $m_i$ 个整数 $t_1, t_2, \dots, t_{m_i}$ $(1 \leq m_i \leq 3 \cdot 10^5, 0 \leq t_1 < t_2 < \dots < t_{m_i} \leq T)$。这些是第 $i$ 个闹钟响起的时刻。 所有 $m_i$ 的总和不超过 $3 \cdot 10^5$。

输出一个整数，即在最优选择 $K$ 个闹钟的情况下，没有闹钟响起的最大时间间隔长度。

### 评分 详细子任务附加限制及分值如下表所示： | 子任务 | 分值 | 附加限制 | | :-: | :-: | :-: | | $1$ | $18$ | $K = N$ | | $2$ | $27$ | 所有 $1 \leq i \leq N$ 均满足 $m_i = 1$ | | $3$ | $20$ | 所有 $m_i$ 的总和最多为 $300$ | | $4$ | $35$ | 无附加限制 | ### 样例解释 在第一个样例中，最优策略是选择前两个闹钟。这样，时间间隔 $(1,4)$ 内就不会受到干扰。该间隔的长度为 $3$，且无法获得更长的无干扰时间间隔。 在第二个样例中，两个闹钟在每个整数时间点都会响起，你必须全部选中。在这种情况下，唯一的无干扰时间间隔位于连续的整数之间。这些间隔的长度均为 $1$。 在第三个样例中，挑战持续 $100$ 秒，但所有闹钟仅在前 $10$ 秒内响起。最优策略是选择最后两个闹钟，这样间隔 $(8,100)$ 内就不会受到干扰。