Description

Sandy and Sue both love collecting cards from crispy noodle snacks.

However, Sue collects cards for the beautiful characters on them, while Sandy collects them to exchange for super cool character figures.

Each card is labeled with a sequence of numbers. The length of the sequence on the $i$-th card is $M_i$. To redeem a character figure, you must first collect $N$ cards. For these $N$ cards, if they all share a common contiguous subarray of length $k$, then you can redeem a figure of level $k$. Identical means: two substrings have the same length, and adding a number to every element of one substring will make it equal to the other.

Sandy has far fewer cards than the required $N$, so Sue decides to give her cards to Sandy for Sandy’s birthday. With Sue’s help, Sandy finally has $N$ cards. However, Sandy does not know which level of figure can be redeemed. Now, please help Sandy and Sue determine the highest level of figure they can get.

Input Format

The first line contains an integer $N$, the minimum number of cards required to redeem a figure, i.e., the number of cards Sandy now has.

For each $i = 1, 2, \dots, N$, the $(i+1)$-th line starts with the length $M_i$ of the $i$-th card’s sequence, followed by $M_i$ integers separated by spaces, where the $j$-th number is the $j$-th element in the sequence.

Output Format

Output a single integer $k$, the maximum obtainable level.

2
2 1 2
3 4 5 9

2

Hint

$30\%$ of the testdata guarantee $n \le 50$.

$100\%$ of the testdata guarantee $n \le 1000, M \le 1000, 2 \le M_i \le 101$.

Update: In the statement, the Constraints for $M_i$ and $M$ are actually the same thing. True Constraints: $40 \le n \le 1000, 2 \le M_i \le 101$, and each number in the sequences is in the range $[0, 1864]$.

Translated by ChatGPT 5