桌面上共有 $$$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希望这个游戏能玩到天荒地老,聪明的你能告诉他这个游戏最多能进行多少轮吗?
第一行 $$$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}$$$ 的全排列。
一行一个整数,表示游戏的最大轮数。
5 3 2 4 1 1 2 1 3 1 5 1 6
2
样例1的解释如下:
第1轮:$$$c=1,2,3$$$,$$$d=1,2,3$$$;
第2轮:$$$c=1,4,5$$$,$$$d=4,5,6$$$。
因此最多进行两轮游戏。