Partmin

Cum finalul semestrului se apropie, este momentul predării eseului la GCEA (Gândire Critică şi Etică Academică). Ca orice student conştiincios, ţi-ai pregătit cu atenţie eseul şi ai avut grijă să aibă exact limita minimă admisă. Înainte de corectare, însă, acesta va fi verificat cu ajutorul unui program Anti-Plagiat, iar în cazul în care acesta va detecta prea multe pasaje comune cu cele conţinute de surse publice, va trebui să repeţi materia.

Detectorul Anti-Plagiat funcţionează pe un principiu atipic. Pentru fiecare paragraf al textului, acesta va calcula un Scor de Identitate egal cu numărul subsecvenţelor palindromice conţinute de acel paragraf.

Scorul total de Identitate al lucrării va fi reprezentat de suma Scorurilor tuturor paragrafelor.

Astfel, pentru a minimiza şansele de a fi acuzat de plagiat pe nedrept, eşti interesat de modul optim de a-ţi împărţi lucrarea în paragrafe pentru ca Scorul de Identitate rezultat să fie minim posibil.

Una din multele condiţii ale eseului, însă, este că numărul de paragrafe al acestuia nu poate depăşi un număr prestabilit $k$, pentru a nu se pierde din coerenţa ideilor.

Cerință

Astfel, dându-se $n$ - lungimea eseului, $k$ şi textul propriu-zis, să se afişeze pentru fiecare $1 \leq i \leq k$ Scorul minim de Identitate al textului dacă îl împărţim în $i$ paragrafe.

Date de intrare

Fişierul de intrare partmin.in va conţine pe prima linie două numere naturale $n$ şi $k$.

Pe cea de-a doua linie se va afla un şir de caractere, fără spaţii, format din litere mici ale alfabetului latin ce reprezintă textul eseului.

Date de ieșire

În fişierul de ieşire partmin.out se vor afla $k$ linii.

Pe linia $i$ a acestuia se va afişa un singur număr natural reprezentând costul minim de a împărţi eseul in $i$ paragrafe.

Restricții și precizări

• O subsecvenţă a unui şir este formată din caractere aflate pe poziţii consecutive în şir.
• Un paragraf al eseului trebuie să reprezinte o subsecvenţă nevidă a acestuia.
• Toate paragrafele sunt disjuncte, iar reuniunea lor este egală cu textul complet.
• $k \leq n$ pentru orice test.
• Pentru teste ce valorează $10$ puncte: $k \leq n \leq 100$
• Pentru alte teste ce valorează $10$ puncte: $2 \leq n \leq 1\ 000$ şi $k = 2$
• Pentru alte teste ce valorează $10$ puncte: $k \leq n \leq 1\ 000$ şi toate caracterele şirului sunt egale.
• Pentru restul testelor: $k \leq n \leq 1\ 000$

Exemplu

partmin.in

5 2
axaxy

partmin.out

7
5

Explicație

Dacă vom lăsa tot textul într-un singur paragraf, acesta va conţine subsecvenţele palindromice:

a, x, a, x, y, axa şi xax.

Pentru două paragrafe putem împărţi textul în: ax şi axy ce vor conţine doar cele $5$ subsecvenţe palindromice formate dintr-un singur caracter.