Cow Cellphone

The cows are designing a special cellphone that uses only a subset of the English alphabet — namely the first L letters — but with fewer, larger buttons. They want to assign the L letters to B buttons in order, so that each button gets a contiguous block of letters. When a cow enters a word (a cow name) using predictive text (by pressing the corresponding button for each letter), the sequence of button presses may correspond to more than one word, causing ambiguity. In order to help the cows communicate clearly, the goal is to choose an assignment that maximizes the number of cow names that can be uniquely identified by their button‐press sequence.

More formally, you are given an integer L (1 ≤ L ≤ 26) representing the number of letters (which are the first L letters of the English alphabet in order). You are also given an integer B (1 ≤ B ≤ L) which is the number of buttons. The letters must be partitioned into B contiguous, nonempty segments. Each segment is assigned a distinct button number (from 1 to B). Then, a cow name is entered as a sequence of button numbers corresponding to its letters. If the same sequence is produced by more than one cow name from the provided dictionary, then none of those cow names are unambiguous.

The input includes a dictionary of cow names (each cow name consists solely of letters from the first L letters) and your task is to find the partition of the alphabet that produces the maximum number of uniquely identifiable cow names. If a cow name’s button‐press sequence is unique among all dictionary words, then it is counted.

Note: All formulae must be written in \( \LaTeX \) format. For example, the constraints above can be written as \(1 \le L \le 26\) and \(1 \le B \le L\).

inputFormat

The first line contains three integers \(L\), \(B\), and \(N\) separated by spaces, where \(L\) is the number of letters in the cow alphabet, \(B\) is the number of buttons on the cellphone, and \(N\) is the number of cow names in the dictionary.

Each of the following \(N\) lines contains a single cow name (a nonempty string composed only of the first \(L\) lowercase English letters).

outputFormat

Output a single integer, which is the maximum number of cow names that can be uniquely determined by their button‐press sequence using an optimal letter-to-button assignment.

sample

5 3 4
abc
abd
abe
bcd

2