题目描述

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

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

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

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

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

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

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

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

输入格式

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

$N\ K$

$S$

输出格式

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

题目大意

题目描述

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

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

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

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

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

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

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

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

输入格式

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

$N\ K$

$S$

输出格式

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

样例解释

在输入样例 1 中，例如 Bitaro 可以执行以下操作。这里下划线表示由 Bitaro 交换的两只岛狸的位置：

• 交换第三只海狸和从右侧舞台开始的第四只海狸。此操作之后，字符串表示从右侧到左侧的海狸部分变为 $\text{`\texttt{AA\underline{AB}BABBAB}'}$。

• 交换第八只海狸和从右侧舞台开始的第九只海狸。此操作之后，字符串表示从右侧到左侧的海狸部分变为 $\text{`\texttt{AAABBAB\underline{AB}B}'}$。

经过这些操作之后，Bitaro 可以如下分配海狸唱哪首歌：

• 从右往左数，第 $1,2,3,4,5,7$ 只海狸唱第一首歌。

• 从右往左数，第 $6,8,9,10$ 只海狸唱第二首歌。

这种方式使所有条件均得到满足。

如果操作次数少于 $2$，则不存在一种满足条件的海狸分配方式。因此输出 $2$。

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$ 均为整数。

子任务编号	分值	限制
$1$	$16$	$N \le 10$
$2$	$24$	$N \le 500$
$3$	$21$	$N \le 5000$
$4$	$26$	$N \le 10^5$
$5$	$13$	无

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