Hamburger Distribution

Interview

Time limit0.5sMemory limit256 MB

Summary

Along a line of N positions holding people and hamburgers, each person can eat a hamburger within distance K; find the maximum number of people served.

Level: Medium4 of 10
Topics: Greedy, Two pointers, String, Implementation
Solved: No attempts yet

Problem

People and hamburgers sit at unit intervals along a long bench-shaped table, as shown below. Each person can eat a hamburger whose distance from their position is at most $K$ .


Hamburger	Person	Hamburger	Person	Hamburger	Person	Hamburger	Hamburger	Person	Person	Hamburger	Person
1	2	3	4	5	6	7	8	9	10	11	12

Consider the case $K = 1$ in the state above. In this case each person can eat only a hamburger adjacent to them. The person at position 10 can eat the hamburger at position 11. At most 5 people can eat a hamburger, as follows.

Person at position 2: hamburger at position 1
Person at position 4: hamburger at position 5
Person at position 6: hamburger at position 7
Person at position 9: hamburger at position 8
Person at position 10: hamburger at position 11
Person at position 12: no hamburger available

When $K = 2$ , all 6 people can eat a hamburger.

Person at position 2: hamburger at position 1
Person at position 4: hamburger at position 3
Person at position 6: hamburger at position 5
Person at position 9: hamburger at position 7
Person at position 10: hamburger at position 8
Person at position 12: hamburger at position 11

Given the length of the table $N$ , the distance $K$ within which a hamburger can be chosen, and the positions of the people and hamburgers, write a program to find the maximum number of people who can eat a hamburger.

Input

The first line contains two integers $N$ and $K$ . The next line contains a string of length $N$ consisting of the characters P (person) and H (hamburger) that gives the positions of the people and hamburgers.

Output

Print the maximum number of people who can eat a hamburger on the first line.

Constraints

$1 \le N \le 20,000$
$1 \le K \le 10$

Examples2

Example 1
Input
```
20 1
HHPHPPHHPPHPPPHPHPHP
```
Expected output
```
8
```
Example 2
Input
```
20 2
HHHHHPPPPPHPHPHPHHHP
```
Expected output
```
7
```