题目描述

在舞台上，有 $2N$ 只海狸排成一列。它们是合唱团的成员。每只海狸唱着高音部或低音部。这些信息由一个字符串 $S$ 给出。具体地，如果 $S$ 的第 $i$ 个字符是 $A$，编号为 $i$ 的海狸（从右边看台来看）唱高音。如果 $S$ 的第 $i$ 个字符是 $B$，编号为 $i$ 的海狸唱低音。有 $N$ 只海狸唱高音，有 $N$ 只海狸唱低音。

从现在起，这些海狸将要演唱 $K$ 首歌。然而，因为所有歌曲非常复杂，每只海狸唱恰好一首歌曲，不会唱其他歌曲。此外，为了使歌声更加美妙，每首歌曲必须满足以下条件：

• 至少有一只海狸唱这首歌。

• 唱这首歌的唱高音和唱低音的海狸数量应当相等。

• 如果只考虑唱这首歌的海狸，所有唱高音的海狸都在唱低音的海狸的右边。

指挥家 Bitaro 想找到一种方案，给出哪些海狸唱哪首歌，满足以上所有条件。由于 Bitaro 特别聪明，他注意到这可能无法实现。为了应对这个问题，Bitaro 将交换相邻两只海狸的位置多次，以便有一种方式可以调配海狸，从而满足上述条件。

由于 Bitaro 认为效率很重要，所以他想最小化要执行的操作数。然而，这是一个非常困难的问题。由于您是一位出色的程序员，Bitaro 请求您解决此问题。

编写一份程序，在给出合唱与演唱歌曲数量 $K$ 的信息时，计算 Bitaro 需要执行的最小操作数。请注意，在本任务的限制下，可以执行操作多次，以便有一种方式可以在海狸之间分配歌曲，满足上述条件。

输入格式

从标准输入读取以下数据:

$N\ K$

$S$

输出格式

向标准输出写入一行。输出应该包含 Bitaro 需要执行的最小操作数。

5 2
AABABABBAB

2

5 3
AABABABBAB

0

3 1
BBBAAA

9

10 3
ABABBBBABBABABABAAAA

37

提示

【样例解释 #1】

在该样例输入中，例如 Bitaro 可以进行如下操作。下划线表示被交换的两个海狸的位置。

1. 交换从舞台右侧数第 3 个和第 4 个海狸。
   操作后，表示海狸部件分布的字符串变为 $\text{`\texttt{AA\underline{AB}BABBAB}'}$。
2. 交换从舞台右侧数第 8 个和第 9 个海狸。
   操作后，字符串变为 $\text{`\texttt{AAABBAB\underline{AB}B}'}$。

操作完成后，Bitaro 可以按如下方式分配歌曲：

• 从舞台右侧数第 1, 2, 3, 4, 5, 7 个海狸演唱第一首歌
• 从舞台右侧数第 6, 8, 9, 10 个海狸演唱第二首歌

这种分配方式满足条件。若操作次数少于 2 次，则不存在满足条件的分配方式。因此输出 2。

该样例满足所有子任务的限制。

【样例解释 #2】

不进行任何操作时，Bitaro 可以按如下方式分配歌曲：

• 从舞台右侧数第 1, 2, 3, 5 个海狸演唱第一首歌
• 从舞台右侧数第 4, 6, 7, 8 个海狸演唱第二首歌
• 从舞台右侧数第 9, 10 个海狸演唱第三首歌

这种分配方式满足条件。因此输出 0。

该样例满足所有子任务的限制。

【样例解释 #3】

该样例满足所有子任务的限制。

【样例解释 #4】

该样例满足所有子任务的限制。

【数据范围】

对于所有测试数据，满足 $1 \le N \le 10^6$，$1 \le K \le N$，$S$ 是长度为 $2N$ 的字符串，且其中字符 $\verb!A!$ 和 $\verb!B!$ 各出现 $N$ 次。保证 $N,K$ 均为整数。

提示说明部分，翻译由 DeepSeek R1 完成