题目描述

Once Charlie decided to start a new life by deleting all files in his Downloads directory. It's easy to do that using $\texttt{bash}$ shell! It has two useful features: the $\texttt{rm}$ command, which removes all files given as arguments, and patterns, which are replaced with the list of files matching them before executing the command.

Charlie ran $\texttt{rm *}$, but received an $\texttt{Argument list too long}$ response. Unfortunately, after $\texttt{bash}$ replaced $\texttt{*}$ with the names of all files in the Downloads directory, it failed to run the command because it had too many arguments.

After some experiments, Charlie realized he can execute $\texttt{rm abc*}$ to delete all files with names starting with $\texttt{abc}$ if there are at most $k$ such files. If more than $k$ files match this pattern, none of them will be deleted. Of course, he can replace $\texttt{abc}$ with any string.

Help Charlie to find the smallest number of $\texttt{rm}$ commands needed to delete all files. Assume that he can only use the $\texttt{rm}$ command as $\texttt{rm <prefix>*}$, where $\texttt{<prefix>}$ consists of lowercase English letters (and can be empty).

输入格式

The first line contains two integers $n$ and $k$ --- the number of files to delete, and the maximum number of files that can be deleted by one $\texttt{rm}$ command ($1 \le n, k \le 3 \cdot 10^5$).

Each of the next $n$ lines contains a single string, denoting a file name. All file names are distinct, non-empty, and consist of lowercase English letters. The total length of all file names doesn't exceed $3 \cdot 10^5$.

输出格式

Print a single integer --- the smallest number of $\texttt{rm}$ commands needed to delete all files.

4 2
a
abc
abd
b

2

4 2
d
c
ab
a

2

5 3
please
remove
all
these
files

3

提示

In the first example test, Charlie can execute $\texttt{rm ab*}$ to delete files $\texttt{abc}$ and $\texttt{abd}$, and then execute $\texttt{rm~*}$ to delete files $\texttt{a}$ and $\texttt{b}$. Note that he can't just run $\texttt{rm *}$ immediately, because initially all four files match an empty prefix.