물리스, 전자, 가위

아마도 여러분들은 '가위 바위 보'라는 게임을 알고 있을 것입니다. 로봇들은 이를 '물리스, 전자, 가위'라 불리는 유사한 게임을 즐겨합니다.

'물리스, 전자, 가위'의 규칙은 간단합니다. 두 로봇이 대결합니다. 두 로봇은 세 번을 세며, 동시에 물리스, 전자 또는 가위의 제스처를 보여줍니다. 물리스는 가위를 이깁니다(가위는 물리스를 부수지 못하기 때문에), 가위는 전자를 이깁니다(가위로 전자를 절단할 수 있기 때문에), 그리고 전자는 물리스를 이깁니다(전자가 물리스에 간섭을 일으키기 때문입니다). 예를 들어, 첫 번째 로봇이 '물리스' 제스처를 하고 두 번째 로봇이 '전자' 제스처를 하면, 두 번째 로봇이 승리합니다. 물론, 두 로봇이 동일한 제스처를 하면 무승부입니다.

개발자 경호는 그의 로봇 R2와 '물리스, 전자, 가위' 게임을 N (1 ≤ N ≤ 100,000)번 하려고 합니다. R2는 이 게임의 전문가로, 경호의 제스처를 그가 내기 전에 예측할 수 있습니다. 그러나, R2는 친환경 로봇으로 효율적으로 설계되어 있어 전체 게임 동안 제스처를 최대 K 번 (0 ≤ K ≤ 20)만 변경할 수 있습니다. 예를 들어, K=2 인 경우, R2는 처음 몇 게임 동안 '물리스'로 진행하고, 그 후 '전자'로 변경하여 일정 횟수를 진행한 후, 마지막 남은 게임은 '물리스'로 변경하여 진행할 수 있습니다.

개발자 경호가 취할 제스처의 순서가 주어질 때, R2가 이길 수 있는 게임의 최대 횟수를 구해주세요.

입력 파일의 첫 번째 줄에는 N과 K가 포함됩니다.

나머지 N 줄에는 경호의 제스처가 담겨 있으며, 각각 H(물리스), P(전자), 또는 S(가위)입니다.

R2가 제스처를 최대 K 번만 변경할 수 있다는 조건 하에, R2가 이길 수 있는 게임의 최대 횟수를 출력합니다.