K.O. Kids

Time limit1sMemory limit1024 MB

Summary

Count how many of k kids cross a 2 x n bridge when each follows the switching strategy and learns the real plates from earlier players.

Level: Easy3 of 10
Topics: Simulation, Implementation
Solved: No attempts yet

Statement

Glen wants to play the most exciting game at his birthday party. The game is called Splash Game. His parents built a bridge that spans the full length of the family pool. The bridge is a $2 \times n$ grid: it has $n$ steps, and each step has two plates. The players cross the bridge one after another in a fixed order. At each of the $n$ steps, one of the two plates is fake. A player who steps onto the fake plate falls into the pool with a big Splaaaaash.

A participant can guess the real plate and stay dry, but she may still fall later. The first player has a hard time. She must guess the real plate at every step to reach the other side. Later players have an advantage because they can see what the others did. For every step already played, they know which plate is real. If someone guesses right, everybody sees it. If someone guesses wrong and falls, everybody knows the other plate is the real one.

The players follow a simple strategy. The first player steps on the left plate at the first step. If she is correct, she switches to the right side, and she keeps switching sides at every step. Each other player, on her turn, follows the correct choices as far as they are known. After that, she applies the switching strategy too: if she stepped on the left plate at the previous step, she now steps on the right one, and vice versa.

The game is only fun if at least a few kids reach the other side, but not too many, since everybody enjoys watching someone fall. Given the number of kids and the layout of fake and real plates, output how many kids reach the other side.

Figure K.1: The bridge layout for the fourth sample case (cracked squares indicate the fake plates). The first player guesses the first step correctly but falls on the second step. The second player knows the correct choices for the first two steps and guesses the third and fourth steps correctly by switching. In the end, three of the seven kids reach the other side.

Input

The input consists of:

One line with integers $n, k$ ( $1 \leq n,k \leq 10^3$ ), the length of the bridge and the number of kids.
One string $s$ of length $n$ consisting of the characters L and R. An L at position $i$ means the real plate at step $i$ is the left one. An R means the right plate is the real one.

Output

Output a single integer, the number of kids who reach the other side of the bridge.

Examples4

Example 1
Input
```
3 5
LRL
```
Expected output
```
5
```
Example 2
Input
```
3 2
RRR
```
Expected output
```
0
```
Example 3
Input
```
3 5
LLL
```
Expected output
```
3
```
Example 4
Input
```
8 7
LLRLLLRR
```
Expected output
```
3
```