DNA Sequencing

A customer brought the body of an alien from outer space to a biology lab and asked the lab to extract its DNA sequence. Unlike life on Earth, this DNA does not use the four nucleotides A, C, G and T. It uses all 26 capital English letters, so every DNA sequence is a string of capital letters. The sequencing machine pulled several DNA sequences out of the tissue and printed them on paper, one per line.

Under the contract a sequence is valid only if its length is at least $M$, and the customer pays one dollar for each distinct valid sequence. The lab may take a correction pen and erase letters from the end of each printed line. The number of erased letters is chosen separately for each line, and erasing nothing is allowed, so each line becomes some prefix of the sequence that was printed on it.

Choose what to erase so that the number of distinct valid sequences left on the paper is as large as possible, then report that number.

The input contains several test cases. The first line of each test case has two space separated integers $k$ and $M$ ($1 \le k \le 500$, $1 \le M \le 500$). Each of the next $k$ lines has an integer $n_i$ and a string $s_i$ separated by a space, which means the sequence $s_i$ was printed on $n_i$ lines of the paper ($1 \le n_i \le 500$). Each $s_i$ consists of capital English letters only and its length is between 1 and 500. The same string may appear on more than one of those lines. The last line of the input is 0 0, and that line is not a test case.

For each test case, print one line with the maximum number of distinct valid sequences the lab can produce.