Hẳn bạn đã từng nghe nói đến trò chơi "Oẳn tù tì" (Rock, Paper, Scissors). Đàn bò thích chơi một trò tương tự mà chúng gọi là "Móng guốc, Giấy, Kéo" (Hoof, Paper, Scissors).

Luật chơi "Móng guốc, Giấy, Kéo" rất đơn giản. Hai con bò đấu với nhau. Cả hai cùng đếm đến ba, rồi đồng thời ra một cử chỉ tượng trưng cho móng guốc, một tờ giấy hoặc một chiếc kéo. Móng guốc thắng kéo (vì móng guốc có thể đập nát kéo), kéo thắng giấy (vì kéo có thể cắt giấy), còn giấy thắng móng guốc (vì móng guốc có thể bị giấy cứa). Chẳng hạn, nếu con bò thứ nhất ra cử chỉ "móng guốc" và con thứ hai ra "giấy", con bò thứ hai sẽ thắng. Tất nhiên, hai bên cũng có thể hòa nếu cùng ra một cử chỉ.

Farmer John muốn đấu với cô bò quý Bessie của mình trong \(N\) ván "Móng guốc, Giấy, Kéo" (\(1 \leq N \leq 100\,000\)). Là một chuyên gia của trò chơi, Bessie có thể đoán trước từng cử chỉ của Farmer John. Đáng tiếc, do là một con bò, Bessie cũng rất lười. Vì vậy, cô thường ra cùng một cử chỉ nhiều lần liên tiếp. Trên thực tế, trong toàn bộ các ván đấu, cô chỉ sẵn lòng đổi cử chỉ nhiều nhất \(K\) lần (\(0 \leq K \leq 20\)). Chẳng hạn, nếu \(K=2\), cô có thể ra "móng guốc" trong vài ván đầu tiên, rồi đổi sang "giấy" trong một khoảng thời gian, sau đó kết thúc các ván còn lại bằng "móng guốc".

Dựa trên dãy cử chỉ Farmer John sẽ ra, hãy xác định số ván lớn nhất Bessie có thể thắng.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(K\).

\(N\) dòng còn lại chứa các cử chỉ của Farmer John, mỗi cử chỉ là H, P hoặc S.

Dữ liệu ra

In số ván lớn nhất Bessie có thể thắng khi cô chỉ được đổi cử chỉ nhiều nhất \(K\) lần.

Ví dụ

5 1
P
P
H
P
S

4

Nguồn

USACO 2017 January Contest, Gold — Hoof, Paper, Scissors. Tác giả đề: Mark Chen và Brian Dean.

https://usaco.org/index.php?page=viewproblem2&cpid=694