K.O. Kids

글렌은 생일 파티에서 가장 재미있는 게임을 하고 싶어 합니다. 게임의 이름은 Splash Game입니다. 부모님이 가족 수영장의 전체 길이를 가로지르는 다리를 만들었습니다. 이 다리는 $2 \times n$ 격자로 볼 수 있습니다. 다리에는 $n$개의 계단이 있고, 각 계단에는 판이 두 개씩 있습니다. 참가자들은 정해진 순서대로 한 명씩 다리를 건넙니다. 각 계단에서 두 판 중 하나는 가짜입니다. 가짜 판을 밟은 사람은 큰 Splaaaaash 소리와 함께 수영장에 빠집니다.

참가자는 진짜 판을 맞히면 물에 빠지지 않지만, 나중 계단에서 빠질 수도 있습니다. 첫 번째 참가자는 힘든 상황에 놓입니다. 반대편에 도달하려면 모든 계단에서 진짜 판을 맞혀야 하기 때문입니다. 뒤에 오는 참가자들은 앞사람들의 행동을 볼 수 있어서 유리합니다. 이미 지나간 계단에서는 어느 판이 진짜인지 알고 있습니다. 누군가 맞히면 모두가 그것을 보게 됩니다. 틀려서 빠졌다면 다른 판이 진짜라는 사실을 모두가 알게 됩니다.

참가자들은 단순한 전략을 따릅니다. 첫 번째 참가자는 첫 계단에서 왼쪽 판을 고릅니다. 맞혔다면 오른쪽으로 옮겨 가고, 이후 계단마다 계속 좌우를 바꿉니다. 나머지 참가자는 차례가 오면 알려진 올바른 선택을 먼저 따르고, 그 뒤에는 같은 방식으로 좌우를 바꿉니다. 즉 직전 계단에서 왼쪽 판을 밟았다면 이번에는 오른쪽 판을 밟고, 그 반대도 마찬가지입니다.

게임은 최소한 몇 명이 반대편에 도달해야 재미있습니다. 하지만 너무 많이 도달해도 재미가 줄어듭니다. 사람이 물에 빠지는 모습을 보고 모두 웃기 때문입니다. 참가자 수와 가짜 판 및 진짜 판의 배치가 주어졌을 때, 반대편에 도달하는 참가자 수를 출력하세요.

그림 K.1: 네 번째 예시 사례의 다리 배치입니다(갈라진 칸이 가짜 판을 나타냅니다). 첫 번째 참가자는 첫 계단을 맞히지만 두 번째 계단에서 빠집니다. 두 번째 참가자는 처음 두 계단의 올바른 선택을 알고 있으며, 좌우를 바꿔 세 번째와 네 번째 계단을 맞힙니다. 결국 7명 중 3명이 반대편에 도달합니다.

입력은 다음과 같습니다.

• 정수 $n, k$ ($1 \leq n,k \leq 10^3$)가 한 줄에 주어집니다. $n$은 다리의 길이이고, $k$는 참가자 수입니다.
• 길이가 $n$인 문자열 $s$가 주어집니다. $s$는 L과 R로 이루어져 있습니다. $i$번째 위치의 L은 $i$번째 계단의 진짜 판이 왼쪽이라는 뜻이고, R은 오른쪽이라는 뜻입니다.

반대편에 도달하는 참가자 수를 정수 하나로 출력합니다.