시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB100454047.059%

문제

Martynas planuoja išvykti į žvejybą ir žvejodamas praleisti k dienų. Žinodamas, kad žuvys geriausiai kimba lietingomis dienomis, Martynas nori pasirinkti tokias k nuoseklių dienų, iš kurių būtų kiek įmanoma daugiau lietingų dienų.

입력

Pirmojoje įvesties eilutėje pateikti du sveikieji skaičiai: N – dienų, kuriomis gali prasidėti išvyka, skaičius, ir k – kiek nuoseklių dienų truks išvyka.

Antroji eilutė nusako N + k − 1 dienų orų prognozes. Joje pateikiami simboliai ci (1 ≤ i ≤ N + k − 1):

  • ci = L, jei i-toji diena yra lietinga;
  • ci = S, jei i-toji diena yra saulėta.

출력

Išveskite vieną skaičių – pirmos išvykos dienos numerį. Martynas nori išvykti žvejoti kuo greičiau, todėl jei yra keli galimi sprendiniai išveskite tą, kurio pirmos dienos numeris yra mažiausias.

제한

  • 1 ≤ k, N ≤ 1 000 000.

예제 입력 1

10 4
SSSLSLSLSSSSS

예제 출력 1

3

Martynas žvejyboje praleis k = 4 dienas:

  • išvykus 1-ąją d. lis 1 dieną: SSSL
  • išvykus 2-ąją d. lis 1 dieną: SSLS
  • išvykus 3-iąją d. lis 2 dienas: SLSL
  • išvykus 4-ąją d. lis 2 dienas: LSLS
  • ir t. t.

Peržiūrėję visus variantus pamatysime, kad 4 dienas trunkančioje išvykoje daugiausia bus 2 lietingos dienos. Anksčiausia tokia išvyka prasidės 3-iąją dieną.