Cerință

Se consideră șirul infinit inf="INFINFINFINF...".

Se dau două numere naturale n și k și un șir de caractere s de lungime n format doar din caracterele 'I' , 'N' și 'F'.

Să se afle numărul minim de modificări ce trebuie realizate în șirul s pentru a obține o subsecvență de lungime k a șirului infinit inf.

O modificare constă în schimbarea unui caracter din șirul s cu un alt caracter din mulțimea {'I','N','F'}.

De exemplu, în urma unei modificări a ultimului caracter, șirul "IIIFN" devine "IIIFF".

Date de intrare

Fișierul de intrare inf.in conține pe prima linie numerele n și k, iar pe a doua linie șirul s format din n caractere.

Date de ieșire

Fișierul de ieșire inf.out va conține pe prima linie numărul de modificări necesare.

Restricții și precizări

• 2 ≤ n ≤ 1.500.000
• 1 ≤ k ≤ 500.000
• k ≤ n
• Rezultatul poate fi 0
• O subsecvență de lungime k a șirului s reprezintă un șir format din k elemente de pe poziții consecutive din șirul s.

Exemplu 1:

inf.in

5 2
FNNNN

inf.out

1

Exemplu 2:

inf.in

5 5
NFFNI

inf.out

2

Explicație:

Exemplul 1: Numărul minim de modificări este 1. Înlocuind primul caracter cu 'I' vom obține subsecvența de lungime 2: "IN".
Exemplul 2: Numărul minim de modificări este 2. Înlocuind al treilea caracter cu 'I' și al cincilea caracter cu 'F' vom obține subsecvența de lungime 5: "NFINF".