Re-Districting in the City of Cows

The cow metropolis, "Cow City," is undergoing redistricting. The city consists of a linear arrangement of n contiguous grass plots. Each plot is occupied by a single cow which is either a Holstein or a Guernsey. The government (controlled by the Holsteins) needs to partition the city into several contiguous districts. Each district must contain at least 1 and at most k plots, and every plot must belong to exactly one district.

For each district, let the number of Holsteins be H and the number of Guernseys be G. A district is considered "bad" (i.e. politically disadvantageous) if the Guernsey count is greater than or equal to the Holstein count. That is, a district is bad if \[ H \le G \] or equivalently, if H is not strictly greater than G.

The objective is to find a partitioning strategy that minimizes the total number of bad districts. Output the minimum possible number of bad districts.

Input Format: The first line contains two integers n and k. The second line contains a string of length n consisting of characters 'H' and 'G', representing Holstein and Guernsey respectively.

Output Format: A single integer representing the minimum possible number of bad districts.

inputFormat

The first line contains two integers n and k (1 ≤ n; 1 ≤ k ≤ n). The second line contains a string of length n consisting only of the characters 'H' and 'G'.

outputFormat

Output a single integer, the minimum number of districts that are bad (i.e. those where the number of Guernseys is greater than or equal to the number of Holsteins).

sample

5 3
HGGHH

1