Bessie's Combo Game

Bessie is playing a game using only three skill keys: A, B, and C. There are n specific combo moves; the i-th combo is represented by a string \(s_i\) (composed only of the letters A, B and C). Bessie will input a string \(t\) of exactly \(k\) characters. For every occurrence of any combo \(s_i\) as a contiguous substring in \(t\), she gains one point. Note that if a combo appears multiple times (even overlapping), each occurrence counts.

Your task is to determine the maximum total score Bessie can achieve by choosing the best possible string \(t\) of length \(k\). More formally, given n patterns \(s_i\) and an integer \(k\), find the maximum possible total number of occurrences of these patterns in any string \(t\) of length \(k\) over the alphabet \(\{A, B, C\}\).

A pattern \(s\) is said to appear in \(t\) at position \(i\) if \(t[i \ldots i+|s|-1] = s\). Overlapping occurrences are counted separately.

inputFormat

The first line contains two integers \(n\) and \(k\) (the number of combo moves and the length of the string).

Each of the next \(n\) lines contains a non-empty string \(s_i\), representing a combo move. Each \(s_i\) consists only of the characters A, B, and C.

outputFormat

Output a single integer—the maximum score Bessie can achieve.

sample

1 3
A

3