발굽, 종이, 가위 (Gold)

"가위바위보" 게임은 들어 봤을 것이다. 소들은 이와 비슷한 "발굽, 종이, 가위"라는 게임을 즐긴다.

"발굽, 종이, 가위"의 규칙은 간단하다. 소 두 마리가 서로 겨룬다. 둘이 함께 셋을 센 다음 동시에 발굽, 종이, 가위 중 하나를 나타내는 동작을 한다. 발굽은 가위를 이기고(발굽으로 가위를 부술 수 있으므로), 가위는 종이를 이기고(가위로 종이를 자를 수 있으므로), 종이는 발굽을 이긴다(발굽이 종이에 베일 수 있으므로). 예를 들어 첫 번째 소가 "발굽"을 내고 두 번째 소가 "종이"를 내면 두 번째 소가 이긴다. 물론 두 소가 같은 동작을 내면 비길 수도 있다.

농부 존은 자신이 아끼는 소 베시와 "발굽, 종이, 가위"를 $N$판 하려고 한다($1 \le N \le 100\,000$). 이 게임의 달인인 베시는 존이 동작을 내기 전에 그 동작을 미리 알 수 있다. 안타깝게도 베시는 소라서 매우 게으르다. 그래서 같은 동작을 여러 판 연속으로 내는 경향이 있다. 실제로 베시는 전체 게임을 통틀어 동작을 최대 $K$번까지만 바꾸려고 한다($0 \le K \le 20$). 예를 들어 $K=2$라면 처음 몇 판은 "발굽"을 내다가 한동안 "종이"로 바꾸고, 남은 판은 다시 "발굽"을 내며 마칠 수 있다.

존이 낼 동작의 순서가 주어질 때, 베시가 이길 수 있는 게임 수의 최댓값을 구하시오.

첫째 줄에 $N$과 $K$가 주어진다.

다음 $N$개의 줄에는 존이 내는 동작이 순서대로 하나씩 주어진다. 각 동작은 H(발굽), P(종이), S(가위) 중 하나이다.

베시가 동작을 최대 $K$번까지만 바꿀 수 있을 때, 이길 수 있는 게임 수의 최댓값을 출력한다.