Problem description

Chłopcy i dziewczęta ustawili się w rzędzie. Niestety, dziewczyny lubią być z dziewczynami i dlatego niektórych chłopców z rzędu należy wyprosić. Chcemy wyprosić jak najmniejszą liczbę chłopców, aby obok siebie stało co najmniej K dziewcząt.

Napisz program, który: wczyta ustawienie początkowe chłopców i dziewcząt, wyznaczy minimalną liczbę chłopców, których należy wyprosić z rzędu i wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna K, określająca liczbę dziewcząt, które mają stać obok siebie.

W drugim wierszu wejścia znajduje się ciąg znaków złożony z liter C i D określający początkowe ustawienie chłopców i dziewcząt zgodnie z kolejnością stania w rządku.

Litera C oznacza chłopca, zaś D oznacza dziewczynkę.

Wyjście

W pierwszym i jedynym wierszu wyjścia powinna się znaleźć jedna liczba całkowita – minimalna liczba chłopców, których należy wyprosić z rządku, aby obok siebie stało co najmniej K dziewcząt.

Jeśli w rzędzie łącznie znajduje się mniej niż K dziewcząt, należy wypisać jedno słowo NIE.

Ograniczenia

1 ≤ K ≤ 10⁶.

Długość ciągu (liczba osób) nie przekracza miliona znaków.

Przykład

3
CDCDD

1

3
DCCCCD

NIE

4
CDDCCDCDDCCCCCDC

3