P13630 [NWRRC 2021] Clean Up!

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 *}$, where $\texttt{}$ 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.

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.