cli

Se dau N cuvinte distincte formate din litere mici ale alfabetului englez (a..z). Tu te afli în fața unui terminal și trebuie să tastezi cuvinte. Se pot folosi două tipuri de operații:

• adaugă ultimul caracter
• șterge ultimul caracter (numai dacă șirul curent este nevid)

Se mai dă un număr natural pozitiv K. Pentru fiecare i de la 1 la K se cere să se aleagă i cuvinte distincte din cele N astfel încat numărul de operații folosite pentru a tasta toate cele i cuvinte să fie minim. Un cuvânt se consideră tastat dacă la un anumit moment de timp șirul scris în terminal este identic cu acest cuvânt.

Date de intrare

Fișierul cli.in conține pe prima linie numerele naturale N și K, iar pe următoarele N linii sunt cele N cuvinte, câte unul pe linie.

Date de ieșire

Fișierul cli.out va conține K linii, pe linia i aflându-se numărul minim de operații folosite pentru a tasta i cuvinte distincte din cele N.

Restricții și precizări

• 1 ≤ K ≤ N
• Suma lungimilor cuvintelor ≤ 1 000 000
• Pentru 10 puncte: N ≤ 18, suma lungimilor cuvintelor ≤ 100
• Pentru alte 20 de puncte: K ≤ 50, suma lungimilor cuvintelor ≤ 500.
• Pentru alte 20 de puncte: K ≤ 50, suma lungimilor cuvintelor ≤ 10 000.
• Pentru alte 30 de puncte: K ≤ 200, suma lungimilor cuvintelor ≤ 100 000.
• Pentru alte 20 de puncte: N * K ≤ 1 000 000
• Linia de comanda începe și trebuie să se termine cu șirul vid pentru fiecare i de la 1 la K .

Exemplu

cli.in

3 3
a
b
absc

cli.out

2
4
10

Explicație

Pentru i = 1, alegem cuvântul a. Numărul de operații este 2: vid -> a -> vid
Pentru i = 2 alegem cuvintele a și b. Avem nevoie de 4 operații pentru a le tasta: vid -> a -> vid -> b -> vid
Pentru i = 3 alegem toate cele 3 cuvinte. Numărul minim de operații este 10.