B. 玩牌
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

桌面上共有 $$$n$$$ 个非空牌堆,第 $$$i$$$ 个牌堆中有 $$$a_i$$$ 张牌,第 $$$i$$$ 个牌堆的第 $$$j$$$ 张牌上的权值记为 $$$b_{i,j}$$$。

现在进行若干轮游戏。具体而言,游戏的第 $$$t$$$ 轮需要从左往右按顺序选出 $$$k$$$ 个牌堆,记为 $$$c_{t,1},c_{t,2},\cdots,c_{t,k}(1\leq c_{t,1}, c_{t,i} \lt c_{t,i+1}, c_{t,k}\leq n)$$$。从这些牌堆中各选择一张牌并取出。从第 $$$c_{t,i}$$$ 个牌堆中取出的牌记为 $$$d_{t,i}$$$,要求满足 $$$\{d_{t,i}\}$$$ 单调递增。

此外,对于游戏的任意两个相邻轮次,还需要满足前一轮的第 $$$k$$$ 张牌小于后一轮的第 $$$1$$$ 张牌,即 $$$d_{t,k} \lt d_{t+1,1}$$$。

当某一轮无法取出满足条件的 $$$k$$$ 张牌时,游戏结束。

DLee希望这个游戏能玩到天荒地老,聪明的你能告诉他这个游戏最多能进行多少轮吗?

Input

第一行 $$$2$$$ 个正整数 $$$n(1\leq n\leq 2\times 10^5),k(1\leq k\leq n)$$$,表示牌堆数量和每轮取出的卡牌数量。

接下来 $$$n$$$ 行,第 $$$i+1$$$ 行表示第 $$$i$$$ 个牌堆的信息,格式为 $$$a_i,b_{i,1},b_{i,2},\cdots,b_{i,a_i}(1\leq a_i,\sum{a_i}\leq 10^6)$$$,含义如上文所示。

数据保证 $$$b_{i,j}$$$ 互不相同,所有牌的权值共同构成 $$$1\sim \sum{a}$$$ 的全排列。

Output

一行一个整数,表示游戏的最大轮数。

Example
Input
5 3
2 4 1
1 2
1 3
1 5
1 6
Output
2
Note

样例1的解释如下:

第1轮:$$$c=1,2,3$$$,$$$d=1,2,3$$$;

第2轮:$$$c=1,4,5$$$,$$$d=4,5,6$$$。

因此最多进行两轮游戏。