题目描述

在漫漫历史长河里，有众多重要事件的发生，这些事件被称为历史景点。 Dr 作为一名时空旅行爱好者，正在筹备他的时间旅行。

Dr 将喜欢的历史景点分成了 $n$ 类，把第 $i$ 类的历史景点集合记为 $S_i$ ，其中第 $i$ 个历史景点集合中的第 $j$ 个历史景点发生时间为 $S_{i,j}$ 。由于两次游览同一类的历史景点会使 Dr 感到无聊，因此他希望从每类历史景点中选出恰好一个历史景点进行游历。

由于一次游历完 $n$ 个景点过于劳累，因此 Dr 决定分成 $k$ 次时间旅行。每次时间旅行他都可以从任意未游历过的历史景点集合中选择任一历史景点作为起点，然后通过时间跳跃依次游历历史景点。但是时间旅行并非一件容易的事，每次时间旅行的最后必须通过时间跳跃回到本次旅行的起点，否则无法确保回到原先的时间线，同时一次旅行只能进行奇数次时间跳跃，不然会导致时间线的混乱。

时间跳跃可以将 Dr 从一个历史景点传送至另一历史景点，但是如果跳跃的起点历史节点发生时间与终点历史节点发生时间相距过近也会轻微影响时间线。因此 Dr 希望规划他的时间旅行方案使得每次时间跳跃的起点与终点距离尽可能远，这样才能使得他对时间线的影响最小，也就是要最大化 $k$ 次旅行中所有时间跳跃的时间差最小值。

如果 Dr 无法通过恰好 $k$ 次旅行遍历 $n$ 类景点则输出 Impossible

注：

1.即使两个历史景点发生在同一时间，但是由于发生地点不同，因此Dr在一次跳跃后只能游历其中一个历史景点，而不能游历该时间点的所有历史景点。

2.若一次旅行只游历一个点，那么这次旅行没有进行过时间跳跃，对时间线没有影响。

一句话题意：从 $n$ 个可重集合中各选出一个数构成一个大小为 $n$ 集合 $T$，并将 $T$ 排列成 $k$ 个奇环，最大化所有环中相邻点差的最小值。

输入格式

第一行读入两个整数 $n$ 和 $k$。表示历史景点种类数及 Dr 准备旅行次数。

接下来 $n$ 行，每行先先入读一个正整数 $t_i$ 表示第 $i$ 类历史景点有 $t_i$ 个。接下来有 $t_i$ 个整数,第 $j$ 个整数表示第 $i$ 类中第 $j$ 个历史景点的发生时间。

输出格式

输出一个整数表示最大化所有时间跳跃中时间差的最小值。

样例数据

样例 1 输入

5 2
1 1
1 2
1 3
1 4
1 5

样例 1 输出

Impossible

样例 2 输入

4 2
2 2 4
1 4
2 6 12
1 7

样例 2 输出

5

样例 2 解释

选择 $n$ 个历史节点为 $[2,4,12,7]$，第一次旅行路线为 $[2\to 7\to 12\to 2]$，第二次旅行路线为 $[4]$。

样例 3 输入

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

样例 3 输出

3

样例 3 解释

选择 $n$ 个历史节点为 $[1,4,5,8,5,7,2,8,2]$,第一次旅行路线为 $[1\to 4\to 7\to 1]$，第二次旅行路线为 $[2\to 5\to 8\to 2]$，第三次旅行路线为 $[2\to 5\to 8\to 2]$。

子任务

• Subtask 1 (3pts): $2≤n≤300,k=1,|S_i|=1$，且所有历史景点发生时间恰好是 $1$ 至 $n$ 的一个排列
• Subtask 2 (8pts): $2≤n≤15,1≤k < n,|S_i|≤2,0≤S_{i,j}≤10^{18}$
• Subtask 3 (5pts): $2≤n≤300,k=1,|S_i|=1,0≤S_{i,j}≤10^{18}$
• Subtask 4 (12pts): $2≤n≤300,1≤k < n,|S_i|=1,0≤S_{i,j}≤10^{18}$
• Subtask 5 (15pts): $2≤n≤100,1≤k < n,|S_i|≤2,0≤S_{i,j}≤10^{18}$
• Subtask 6 (24pts): $2≤n≤200,1≤k < n,|S_i|≤4,0≤S_{i,j}≤10^{18}$
• Subtask 7 (33pts): $2≤n≤300,1≤k < n,|S_i|≤5,0≤S_{i,j}≤10^{18}$