P2564 [SCOI2009] Birthday Gift

Sichuan 2009 NOI Qualifier.

Xiaoxi has a very long ribbon with various colored beads hanging on it. There are $N$ beads in total, divided into $K$ types. Simply put, we can model the ribbon as the x-axis, and each bead corresponds to a coordinate (i.e., a position). Some coordinates may have no bead, and multiple beads may appear at the same position. Xiaobu’s birthday is coming, so Xiaoxi plans to cut a segment of the ribbon as a gift. To make the gift look nice, she wants this segment to contain all types of beads. For convenience, she also wants the segment to be as short as possible. Can you help Xiaoxi find this minimum length? The length of a ribbon segment is the difference between the end position and the start position.

The first line contains two integers $N, K$, the total number of beads and the number of types. For each of the next $K$ lines, the first number is $T_i$, the count of beads of type $i$. On the same line, $T_i$ non-negative integers are then given in ascending order, representing the positions where these $T_i$ beads appear.

Output a single line: the minimum possible ribbon length.

Sample explanation: There are multiple valid choices. Among the shorter ones are 1 ~ 5 and 5 ~ 8. The latter has length 3, which is shorter, so the answer is 3. Constraints: - For 50% of the testdata, $N \le 10^4$. - For 80% of the testdata, $N \le 8 \times 10^5$. - For 100% of the testdata, $1 \le N \le 10^6, 1 \le K \le 60$, $0 \le$ bead position $< 2^{31}$, and $\sum T_i = N$. Translated by ChatGPT 5