Kpartit

Un șir $x$ format din literele $x_0, x_1, ..., x_{n-1}$ cu $n > 0$ se numește kpartit de ordin k dacă există $k$ și $p_1, p_2, ..., p_{k-1}$ cu proprietățile:

• $0 < k \leq n$
• $0<p_1 < p_2< \ldots <p_{k-1}< n$
• $x_i=x_j$ pentru orice $0 \leq i < j < p_1$
• $x_i=x_j$ pentru orice $p_1 \leq i < j < p_2$
• $\ldots$
• $x_i=x_j$ pentru orice $p_{k-1} \leq i < j < n$
• $x_{p_1-1} \neq x_{p_1}, x_{p_2-1} \neq x_{p_2}, \dots, x_{p_k-1} \neq x_{p_k}$

De exemplu șirurile de lungime $8$ bbbawwww și daaaaddd sunt kpartite de ordinul $3$, șirul de litere de lungime $10$ eeeeezzzzz este kpartit de ordinul $2$, iar șirul de lungime $5$ yyyyy este kpartit de ordinul $1$.

Cerință

Scrieţi un program care, pentru un șir de litere $x=(x_0, x_1, \dots, x_{n-1})$ de lungime $n$ și un număr natural $k$, $0 < k \leq n$ determină numărul minim de litere care trebuie eliminate din $x$ astfel încât acesta să devină kpartit de ordin $k$. În cazul în care acest lucru nu e posibil, se va afișa $-1$.

Date de intrare

Pe prima linie se află numerele $n$ și $k$, separate printr-un spațiu, cu semnificația de mai sus iar pe cea de-a doua linie termenii șirului dat $x_0, x_1, \dots, x_{n-1}$. Aceștia nu vor fi separați prin spații.

Date de ieșire

Pe prima linie se află un singur număr natural, reprezentând rezultatul determinat.

Restricții și precizări

• $1 \leq k \leq n \leq 5 \ 000$;
• Șirul $x$ este format doar din litere mici ale alfabetului englez.

Exemplul 1

stdin

8 3
bbbawwww

stdout

0

Explicație

Nu este necesară eliminarea niciunei litere.

Exemplul 2

stdin

8 2
bbbawwww

stdout

1

Explicație

Este suficientă eliminarea unei litere a astfel încât șirul dat să devină kpartit de ordin $2$.

Exemplul 3

stdin

10 5
eeeeezzzzz

stdout

-1

Explicație

Nu este posibilă obținerea unui șir kpartit de ordinul $5$ prin eliminarea unor litere ale șirului dat.

Exemplul 4

stdin

10 2
bcbbxxbccc

stdout

3

Explicație

Este suficientă eliminarea unei litere c și a celor două litere x astfel încât șirul dat să devină kpartit de ordin $2$.