Fotografen

En fotograf har tagit många fina foton med sin digitalkamera och kopplar in den i sin dator för att överföra bilderna. Bilderna har tagits med olika vridningar av kameran så nu är vissa av bilderna roterade. Vi kallar de fyra möjliga rotationerna ett foto kan ha för upp, höger, ner och vänster och definierar det som den sida som motsvarar uppåt i bilden. En bild är vänd rätt om den är roterad upp. Datorn visar bilderna i en lista och har en funktion som roterar en bild $90^\circ $ medurs. Rotationen sker alltså enligt följande ordning:

Fotografen tycker det verkar tråkigt att rotera foton och bestämmer sig för att göra det till ett roligt spel. Fotografen väljer ett positivt heltal $k$ och bestämmer att det enda sättet att rotera foton är att markera exakt $k$ intill varandra liggande foton ur listan och rotera alla dessa samtidigt. Formellt har fotografen $N$ foton, kalla dem $a_1, a_2, \dots a_ N$. Fotografen kan nu välja ett index $i$ ($1 \leq i \leq N-k+1$) och bilderna $a_ i, a_{i+1}, ... , a_{i+k-1}$ roteras då $90^\circ $ medurs. Detta kallar vi en operation.

Målet med spelet är att vända alla foton rätt med så få operationer som möjligt. Skriv ett program som beräknar det minsta antalet operationer som krävs.

Indata

På första raden står två heltal $N$ och $k$ ($1 \leq k \leq N \leq 100\, 000$), antalet foton totalt respektive antalet foton som måste roteras samtidigt. På andra raden står $N$ tecken som representerar fotografiernas rotation från början: U för upp, H för höger, N för ner och V för vänster.

Utdata

Skriv ut det minsta antalet operationer som krävs. Om det inte går att vända alla foton rätt, skriv ut $-1$.

Poängsättning

I det här problemet kan du samla en del av poängen utan att lösa problemet fullständigt. Ditt program kommer att köras på $10$ testdatagrupper. För varje testdatagrupp to klarar får du $10$ poäng.

• I testdatagrupper värda 10 poäng så kommer $N$ vara maximalt 10.

• I testdatagrupper värda ytterligare 40 poäng så kommer $N$ vara maximalt $5\, 000$.

Exempel

För det första exempelindatat så är en möjlig optimal lösning denna. Rotera tre gånger på position 3-4 för att få UVVU, rotera sedan en gång på position 2-3 för att slutligen få UUUU, och vi är klara med fyra operationer utförda.

4 2
UVUH

4

8 5
HUNVVNVH

9

5 2
UUUUV

-1