题目描述
有$N$个字符串, 每一次操作可以任意选择一个字符串T
.(可以为空串并且不一定是题目所给的字符串) 然后考虑所有还没有被删除的字符串S
, 如果T
是S
的一个前缀(空串是任意串的前缀), 那么把它加入候选删除集合.
但是每一次操作最多删除$K$个字符串, 也就是说如果候选集合中字符串的数量大于$K$, 那么什么也不会发生. 否则, 删除其中所有的字符串.
求出最少需要多少次操作才能删掉所有的字符串.
输入格式
第一行输入两个正整数$N$和$K$. 如题意所示.
接下来$N$行, 每一行输入一个仅包含小写英文字母的字符串.
数据保证没有两个相同的字符串.
对于所有数据 满足$1 \leq N \leq 100$, $1 \leq K \leq 20$, $\sum{len} <= 3 * 10^5$. (所有字符串的长度之和)
输出格式
一行输出一个正整数, 表示最少需要多少次操作才能删除所有字符串.
样例输入1
4 2
a
abc
abd
b
样例输出1
2
样例1解释
我们可以第一次操作选择ab
. 删掉abc
和abd
.
第二次操作选择空串. 将剩下的所有字符串删掉.
样例输入2
4 2
d
c
ab
a
样例输出2
2
样例输入3
5 3
please
remove
all
these
files
样例输出3
3