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é