Zadanie

Jódlovanie

Počet bodov: 60, časový limit: 400ms

Ovečky sa učili jódlovať. Žiaľ, ich hudobný repertoár je obmedzený a zvládajú ako tak ákať, békať a cékať. Po dlhom skúšaní tohoto hudobého umenia došli k tomu, že niektoré kombinácie zvukov znejú lepšie ako iné. Konkrétne, existuje \(k\) kombinácií, ktoré sú krásne.

Ovečky sa rozhodli zložiť si novú pesničku, ktorá bude pozostávať z \(n\) zvukov, a bude čo najkrajšia. Krása piesne je počet výskytov (aj prekrývajúcich sa) jednotlivých krásnych kombinácii.

Zistite koľko najviac krásnych kombinácií môžu dostať.

Úloha

Na prvom riadku dostanete číslo \(0 < k \leq 20\), počet kombinácií a číslo \(n \leq 1000\), dĺžku pesničky.

Na ďalších \(k\) riadkoch dostanete kombinácie. Kombinácia je string znakov ABC. Kombinácie budú navzájom rôzne a ich dĺžka nepresiahne \(15\) znakov.

Príklady

Input:

3 7
ABA
CB
ABACB

Output:

4

Ovečky môžu zaspievať ABACBCB. Zaspievajú tak raz ábéá, raz ábéácé a dvakrát cébé