题目描述

小西有一条很长的彩带，上面挂着 $N$ 颗彩珠，分为 $K$ 种。彩带可以抽象为一条 $x$ 轴，每颗彩珠有一个坐标位置。同一位置可以有多颗彩珠。

小西打算剪一段彩带送给小布，要求这段彩带中包含所有 $K$ 种彩珠，且长度尽可能短。彩带的长度定义为起始位置到结束位置的距离差。

输入格式

第一行两个整数 $N, K$，分别表示彩珠总数和种类数。

接下来 $K$ 行，每行第一个整数 $T_i$ 表示第 $i$ 种彩珠的数量，随后 $T_i$ 个升序排列的非负整数表示各彩珠的位置。保证 $\sum T_i = N$。

输出格式

一行一个整数，表示最短彩带长度。

样例

6 3
1 5
2 1 7
3 1 3 8

3

提示

样例说明

$6$ 颗彩珠，$3$ 种。位置分别为：第 $1$ 种 $\{5\}$，第 $2$ 种 $\{1, 7\}$，第 $3$ 种 $\{1, 3, 8\}$。

区间 $[5,8]$ 包含 $5(\text{种}1), 7(\text{种}2), 8(\text{种}3)$，长度 $3$，是最短的合法方案。

数据范围

对于 $50\%$ 的数据，$N \le 10^4$；

对于 $80\%$ 的数据，$N \le 8 \times 10^5$；

对于 $100\%$ 的数据，$1 \le N \le 10^6$，$1 \le K \le 60$，$0 \le$ 位置 $< 2^{31}$。