문제

가위바위보 게임은 누구나 한 번쯤 들어봤을 법한 유명한 게임이다. 현욱이와 우솔이는 이와 비슷한 '발톱-보-가위' 게임을 즐겨 한다.

'발톱-보-가위' 게임의 규칙은 매우 간단하다. 두 사람이 동시에 발톱(Hoof), 보(Paper), 가위(Scissors) 중 하나를 낸다. 발톱은 가위를 이기고(발톱으로 가위를 부술 수 있다), 가위는 보를 이기며(가위로 종이를 자를 수 있다), 보는 발톱을 이긴다(종이에 발톱이 베일 수 있다). 예를 들어, 첫 번째 사람이 '발톱'을 내고 두 번째 사람이 '보'를 냈다면 두 번째 사람이 승리한다. 물론 두 사람이 같은 것을 내면 비기게 된다.

현욱이는 우솔이와 총 $N$번의 게임을 하려 한다. ($1 \le N \le 100\,000$) 우솔이는 이 게임의 전문가라 현욱이가 각 판에 어떤 동작을 취할지 미리 모두 예측할 수 있다. 하지만 우솔이는 매우 게을러서, 게임을 진행하는 동안 내는 동작을 가급적 바꾸고 싶어 하지 않는다. 사실 우솔이는 $N$번의 게임 전체에서 동작을 최대 $K$번까지만 바꾸려고 한다. ($0 \le K \le 20$)

예를 들어 $K=2$라면, 우솔이는 처음 몇 판 동안 '발톱'을 내다가 중간에 '보'로 한 번 바꾸고, 다시 남은 게임 동안 '발톱'으로 바꾸어 진행할 수 있다.

현욱이가 낼 동작의 순서가 주어졌을 때, 우솔이가 이길 수 있는 최대 게임 횟수를 구하시오.

입력

첫째 줄에 $N$과 $K$가 공백으로 구분되어 주어진다. ($1 \le N \le 100\,000$; $0 \le K \le 20$)

이어서 $N$개의 줄에 현욱이가 내는 동작이 한 줄에 하나씩 H, P, S 중 하나로 주어진다. H는 발톱(Hoof), P는 보(Paper), S는 가위(Scissors)를 의미한다.

출력

우솔이가 동작을 최대 $K$번 바꿀 수 있을 때, 이길 수 있는 최대 게임 횟수를 출력한다.

예제 입력 1

5 1
P
P
H
P
S

예제 출력 1

4