Problem B
Alarms

Your friend Emil has a large collection of alarms that go off at different times, to wake him up and remind him of various things. He has challenged you to choose some of his alarms and spend some time with them. You decide to choose the alarms in such a way that there is a period of time that is undisturbed that is as long as possible, so you can get some sleep.

Emil has $N$ alarms. The challenge is to choose $K$ of these alarms, and spend $T$ seconds with them. These $T$ seconds are the continuous time interval between $t=0$ and $t=T$. The $i$th of Emil’s alarms goes off at times $t_1, t_2, \dots , t_{m_i}$, where $m_i$ is a positive integer. Your task is to find the maximum possible length of a time interval $(L,R)$, where $0 \leq L \leq R \leq T$, such that none of the $K$ chosen alarms go off during that time. Note that the time interval is open (i.e., consists of all times $t$ such that $L < t < R$). So it is OK if an alarm goes off at $t = L$ or $t = R$.

Input

The first line contains three integers $N$, $K$, and $T$ ($1 \leq K \leq N \leq 3 \cdot 10^5$, $1 \leq T \leq 10^9$). These are the number of alarms Emil has, the number of alarms you should pick, and the amount of time the challenge takes place.

The following $N$ lines each contain a positive integer $m_i$, followed by $m_i$ integers $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$). These are the times the $i$th alarm goes off.

The sum of all numbers $m_i$ will not exceed $3 \cdot 10^5$.

Output

Print one integer, the maximum length of a time interval where no alarms go off, if you choose $K$ alarms optimally.

Scoring

Your solution will be tested on a set of test groups. To earn points for a group, you must pass all test cases in that group.

Explanation of Samples

In the first sample, the optimal strategy is to choose the first two alarms. That way, the time interval $(1,4)$ is undisturbed. This interval has length $3$, and it is not possible to get a longer undisturbed time interval.

In the second sample, both alarms go off at every integer time and you have to pick both of them. In this case, the only undisturbed time intervals are in between consecutive integers. These all have length $1$.

In the third sample, the challenge takes place during $100$ seconds, but all the alarms only go off during the first $10$ seconds. The optimal strategy is to pick the last two alarms, so that the interval $(8,100)$ is undisturbed.

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