Alice and Bob are at war. They have a piece of land of dimension \(N*1\) square meter, divided into a vector of squares of dimension \(1*1\) square meter. Some of those squares are Alice's territory and the rest are Bob's. Hence, we can denote the land using a string \(S\) of length \(N\) consisting of 'A' (denoting land owned by Alice) and 'B' (denoting land owned by Bob).

The entire string has to be partitioned into disjoint substrings (substrings of length at most \(K\)). A partition is said to be controlled by a person if the majority of the land is owned by the person in that particular partition. In the case of a tie, no one owns the partition.

Alice is greedy, hence she wants to find out the minimum number of partitions that can't be owned by her.

Input Constraints

First-line has \(N,K\).

Second-line has string \(S\).

Output Constraints

Print the answer.

Constraints

\(1 \leq N, K \leq 5*10^{5} \\ (S[i] = A, B) \forall 1 \leq i \leq N\)