删库

题目描述

有$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

样例输入 2

4 2 
d
c 
ab 
a

样例输出 2

2

样例输入 3

5 3 
please 
remove 
all 
these 
files

样例输出 3

3

样例解释

我们可以第一次操作选择ab. 删掉abc和abd.

第二次操作选择空串. 将剩下的所有字符串删掉.