Divine Bull Computer Lab Assignment

In a certain school, there are two legendary figures, Divine Bull A and Divine Bull B. Every new student has already ardently worshiped exactly one of these divine bulls. Now, the teacher needs to partition the students into computer labs. Since the students are arranged in a line, the teacher can only choose a contiguous segment of students to assign into one computer lab.

For each chosen segment (lab), one of the following conditions must hold:

• All students in the lab worship the same divine bull, or
• If both types of worshippers are present, let \(a\) be the number of students who worship Divine Bull A and \(b\) be the number of students who worship Divine Bull B. It must be that \(|a - b| \leq m\).

You are given the number of students \(n\) and the non-negative integer \(m\). In the second line, you are given a string of length \(n\); each character is either A or B, representing the divine bull the student worships.

Your task is to determine the minimum number of computer labs that the teacher needs so that every lab (i.e. every contiguous segment) satisfies one of the above conditions.

The mathematical condition for a segment spanning indices \(j+1\) to \(i\) (1-indexed) is either:

\[ \text{Either } (\#A = 0 \text{ or } \#B = 0), \quad \text{or} \quad |\#A - \#B| \leq m, \] where \(\#A\) and \(\#B\) denote the counts of A and B respectively, and \(m \ge 0\) is a given integer.

inputFormat

The input consists of two lines:

1. The first line contains two integers \(n\) and \(m\) separated by a space, where \(1 \leq n \leq 10^5\) and \(0 \leq m \leq n\).
2. The second line contains a string of length \(n\) with characters A or B only.

outputFormat

Output a single integer: the minimum number of computer labs (contiguous segments) needed such that each lab satisfies the condition mentioned in the problem.

sample

5 1
AABBA

2