Se citesc n task-uri (fiecare reprezentat printr-o litera indicand tipul sau) si un numar natural k. Intre doua executii ale task-urilor de ACELASI tip trebuie sa treaca cel putin k unitati de timp (CPU-ul poate ramane inactiv o unitate de timp daca niciun task nu poate fi executat in acel moment). Determinati, folosind metoda Greedy, numarul minim de unitati de timp necesare pentru a executa toate task-urile.
- Date de intrare
- Pe prima linie se citeste sirul de task-uri (litere mari). Pe a doua linie se citeste k.
- Date de iesire
- Se afiseaza un singur numar: numarul minim de unitati de timp necesare.
- Restrictii
- 1 <= lungimea sirului <= 100000, 0 <= k <= 100
Exemple
Exemplul 1
Intrare
AAABBB 2
Iesire
8
Exemplul 2
Intrare
AAAAA 2
Iesire
13