3. Záchrana princeznej

Jimi si nedávno kúpil nový herný počítač a jeho štúdium tým značne utrpelo. Je veľmi ťažké učiť sa, keď máte na výber z toľkých dobrých hier. Preto si vytvoril rozvrh, v ktorom má každú hodinu označenú ako pracovnú alebo hernú. Po čase hrania ale Jimiho prestalo baviť zabíjanie príšer a rozhodol sa splniť veľkú úlohu – zachráni princeznú ukrytú na hmlistom ostrove.

Hra však nepodporuje ukladanie počas plnenia misie a preto Jimi nemôže pracovať, kým nezachráni princeznú. Nechce si ale veľmi meniť rozvrh, preto len vyškrtne niektoré pracovné hodiny z rozvrhu tak, aby si vytvoril dostatočne dlhý súvislý úsek herného času na záchranu princeznej. Jeho štúdium je však už teraz riadne zanedbané, a preto chce obetovať čo najmenej zo svojho pracovného času.

Úloha

Jimiho rozvrh vyzerá ako jedna dlhá postupnosť znakov P a H, ktoré označujú pracovné a herné hodiny.

Jimi si vypočítal, že na záchranu princeznej bude potrebovať \(c\) hodín hry.

Vašou úlohou je zistiť, koľko najmenej hodín práce vie vyškrtnúť z rozvrhu tak, aby mal aspoň \(\mathbf{c}\) hodín hry v jednom kuse.

Môžete predpokladať, že herných hodín je v rozvrhu vždy aspoň \(c\).

Formát vstupu

V prvom riadku je číslo \(c\) – počet hodín potrebných na záchranu princeznej. V druhom riadku je rozvrh – reťazec znakov P a H dĺžky \(n\).

Pre vstupy platí \(1 \leq c \leq n \leq 1\,000\,000\).

Formát výstupu

Vypíšte jedno číslo – najmenší počet hodín práce, ktoré treba vyškrtnúť z rozvrhu. Výstup ukončite znakom nového riadku.

Príklad

Input:

3
PPHHPPPHPHPHPPP

Output:

2

Upravený rozvrh vyzerá takto: PPHHPPPHHHPPP.

Input:

4
HHPPPHHPPHHHPH

Output:

1

Input:

2
HHPPHPP

Output:

0