背景

翻译来源：loj #5709. 「NordicOI 2026」Alarms。

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$ 个闹钟的情况下，没有闹钟响起的最大时间间隔长度。

3 2 5
1 1
1 4
2 2 3

3

2 2 7
8 0 1 2 3 4 5 6 7
8 0 1 2 3 4 5 6 7

1

3 2 100
1 10
3 0 2 3
4 3 5 6 8

92

提示

评分

详细子任务附加限制及分值如下表所示：

样例解释

在第一个样例中，最优策略是选择前两个闹钟。这样，时间间隔 $(1,4)$ 内就不会受到干扰。该间隔的长度为 $3$，且无法获得更长的无干扰时间间隔。

在第二个样例中，两个闹钟在每个整数时间点都会响起，你必须全部选中。在这种情况下，唯一的无干扰时间间隔位于连续的整数之间。这些间隔的长度均为 $1$。

在第三个样例中，挑战持续 $100$ 秒，但所有闹钟仅在前 $10$ 秒内响起。最优策略是选择最后两个闹钟，这样间隔 $(8,100)$ 内就不会受到干扰。