Deleting the Database

Problem Description

There are $N$ strings. In one operation, you may choose any string $T$ (which may be empty, and is not necessarily among the given strings). Then consider all strings $S$ that have not been deleted yet; if $T$ is a prefix of $S$ (the empty string is a prefix of any string), add $S$ to the candidate deletion set.

However, at most $K$ strings may be deleted in one operation: if the candidate set contains more than $K$ strings, nothing happens. Otherwise, all strings in the candidate set are deleted.

Find the minimum number of operations needed to delete all the strings.

Input Format

The first line contains two positive integers $N$ and $K$, as described above.

The next $N$ lines each contain one string consisting only of lowercase English letters.

It is guaranteed that no two strings are identical.

For all test cases, $1 \le N \le 100$, $1 \le K \le 20$, and $\sum \text{len} \le 3 \times 10^5$ (the sum of the lengths of all strings).

Output Format

Output one line containing a single positive integer: the minimum number of operations needed to delete all the strings.

Sample Input 1

4 2
a
abc
abd
b

Sample Output 1

2

Sample Input 2

4 2
d
c
ab
a

Sample Output 2

2

Sample Input 3

5 3
please
remove
all
these
files

Sample Output 3

3

Sample Explanation

In the first test case, in the first operation we choose ab, deleting abc and abd. In the second operation we choose the empty string, deleting all the remaining strings.