#P4698. Sdoi2008 Sandy的卡片

    ID: 3830 传统题 1000ms 128MiB 尝试: 1011 已通过: 371 难度: 7 上传者: 标签>CF2200提高+/省选-差分转化后缀数组倍增计数排序Kasai 算法二分答案时间戳避免清空数组

Sdoi2008 Sandy的卡片

[SDOI2008] Sandy 的卡片

题目描述

Sandy 和 Sue 都热衷于收集干脆面中的卡片。

然而,Sue 收集卡片是因为卡片上漂亮的人物形象,而 Sandy 则是为了积攒卡片兑换超炫的人物模型。

每一张卡片都由一些数字进行标记,第 ii 张卡片的序列长度为 MiM_i,要想兑换人物模型,首先必须要集够 NN 张卡片,对于这 NN 张卡片,如果他们都有一个相同的子串长度为 kk,则可以兑换一个等级为 kk 的人物模型。相同的定义为:两个子串长度相同且一个串的全部元素加上一个数就会变成另一个串。

Sandy 的卡片数远远小于要求的 NN,于是 Sue 决定在 Sandy 的生日将自己的卡片送给 Sandy,在 Sue 的帮助下,Sandy 终于集够了 NN 张卡片,但是,Sandy 并不清楚他可以兑换到哪个等级的人物模型,现在,请你帮助 Sandy 和 Sue,看看他们最高能够得到哪个等级的人物模型。

输入格式

第一行为一个数 NN,表示可以兑换人物模型最少需要的卡片数,即 Sandy 现在有的卡片数。

第 i+1i+1 行到第 i+Ni+N 行每行第一个数为第 ii 张卡片序列的长度 MiM_i,之后 j+1j+1 到 j+1+Mij+1+M_i 个数,用空格分隔,分别表示序列中的第 jj 个数。

输出格式

一个数 kk,表示可以获得的最高等级。

样例 #1

样例输入 #1

2
2 1 2
3 4 5 9

样例输出 #1

2

提示

30%30\% 的数据保证 n≤50n\le50

100%100\% 的数据保证 n≤1000,M≤1000,2≤Mi≤101n\le1000,M\le1000,2\le M_i\le101

update:题面上数据范围 MiM_i 和 MM 的范围其实是一个东西… 真实数据范围: 40≤n≤1000,2≤Mi≤10140\le n\le1000,2\le M_i\le101,字符串中的每个数字的大小范围为 [0,1864][0,1864]。