问题描述

在一个操场的一侧直线跑道上摆放着 N 个石子，每个石子有一种颜色。

不同的石子可能有相同的颜色。一共有 K 种颜色。同一位置处可能有多个石子。

现在要选择一段区间，使得该区间包含所有颜色的石子，且该区间的长度最短。

输出这个最短区间的长度。

输入

第一行，两个整数 N K

接下来 K 行：其中第 i 行首先是一个整数 Mi，表示第 i 种颜色的石子的数目；接下来按非降序给出 Mi 个非负整数，表示这 Mi 个石子距离跑道最左侧的距离。数据保证 ∑Mi = N

输出

一个整数，表示满足题意的最短区间的长度

样例输入

7 3
2 8 9
2 1 9
3 1 1 5

样例输出

4

数据范围

对于 50% 的数据， N≤10000；

对于 80% 的数据， N≤800000；

对于 100% 的数据，1≤N≤1000000，1≤K≤60，数据保证 $\sum M_i = N$，所有的距离均为不超过 $2^{31}$ 的非负整数，且保证每一行的距离按非降序给出。