题目描述
Description
尽管牛郎已经收集到了尽可能多的菖蒲,但仍无法满足王母娘娘刁钻的要求。牛郎和织女必须面对见面时间减半这一残酷现实。所幸两人早有约定,将各自最想说的话镂刻在柠檬草叶上,只等来年七夕重聚时交与对方。
织女一共准备有N片柠檬草叶,每一片柠檬草叶上都镂刻有一段长为Li的文字。为了顺利通过天兵天将的重重审查,最想说的话不能够连续出现,即每两个关键字之间必须间隔有K个无关字符。
已知最想说的话一定在每段话中都出现过,并且是长度最长的一句话。你能帮助牛郎参透织女的心事吗?
Constraints
对于40%的数据Li≤10000,N=2;
对于全部的数据Li≤100000,∑Li≤200000,N≤20,K<=1000;
所有汉字序号均为100000以内非零整数。
Time Limit:
前50%的数据时限1S;
后50%的数据时限3S;
Memory Limit:
内存限制65536KB。
输入格式
第一行两个整数N,K,意义见题目描述。
第二行至第N+1行,每行描述一片柠檬草叶。行首一个整数Li,表示这段话的长度。其后Li个整数,分别代表对应汉字在字典中的序号。
输出格式
输出一行整数,即织女最想说的话。
如果解不唯一,则输出字典序最小的答案。
样例输入
样例输出