알람

당신의 친구 Emil은 서로 다른 시간에 울려서 잠을 깨우고 여러 가지 일을 상기시켜 주는 알람을 많이 가지고 있다. 그는 당신에게 자신의 알람 중 일부를 골라 일정 시간 동안 함께 지내는 도전을 제안했다. 당신은 잠을 좀 잘 수 있도록, 방해받지 않는 시간 구간이 가능한 한 길어지게 알람을 고르기로 한다.

Emil은 $N$개의 알람을 가지고 있다. 이 도전에서는 이 알람 중 $K$개를 고르고, 그것들과 $T$초를 보내야 한다. 이 $T$초는 $t=0$와 $t=T$ 사이의 연속된 시간 구간이다. Emil의 $i$번째 알람은 $t_1, t_2, \dots, t_{m_i}$인 시각에 울리며, 여기서 $m_i$는 양의 정수이다. 당신의 과제는 $0 \leq L \leq R \leq T$인 시간 구간 $(L,R)$ 중, 선택한 $K$개의 알람이 그 시간 동안 하나도 울리지 않도록 하는 구간 길이의 가능한 최댓값을 구하는 것이다. 시간 구간은 열린 구간임에 유의하라(즉, $L < t < R$를 만족하는 모든 시각 $t$로 이루어진다). 따라서 알람이 $t = L$ 또는 $t = R$에 울려도 OK이다.

채점

제출한 풀이는 여러 테스트 그룹으로 이루어진 테스트 세트로 평가된다. 한 그룹의 점수를 얻으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 점수 | 제한 조건

$1$ |$18$| $K = N$

$2$ |$27$| 모든 $1 \leq i \leq N$에 대해 $m_i = 1$.

$3$ |$20$| 모든 수 $m_i$의 합은 최대 $300$이다.

$4$ |$35$| 추가 제한 조건이 없다.

첫째 줄에 세 정수 $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,4)$가 방해받지 않는다. 이 구간의 길이는 $3$이며, 이보다 더 긴 방해받지 않는 시간 구간을 얻는 것은 불가능하다.

두 번째 예제에서는 두 알람 모두 모든 정수 시각에 울리며, 두 알람을 모두 골라야 한다. 이 경우 방해받지 않는 시간 구간은 연속한 두 정수 사이의 구간뿐이다. 이 구간들의 길이는 모두 $1$이다.

세 번째 예제에서 도전은 $100$초 동안 진행되지만, 모든 알람은 처음 $10$초 동안에만 울린다. 최적의 전략은 마지막 두 알람을 고르는 것이며, 그러면 구간 $(8,100)$가 방해받지 않는다.