题目描述

On the stage, $2N$ beavers are standing in a row. They are members of the chorus. Each beaver sings either the alto part or the bass part of the chorus. This information is given by a string $S$. Precisely, the $i$-th beaver ($1\le i\le 2N$) from the stage right (i.e., from left when seen from the audience seats) sings the alto part if the $i$-th character of $S$ is $\text{`\texttt{A}'}$. The $i$-th beaver sings the bass part if the $i$-th character of S is $\text{`\texttt{B}'}$. There are $N$ beavers singing the alto part, and $N$ beavers singing the bass part.

From now, the beavers will sing $K$ songs. However, since all the songs are very difficult, each beaver sings exactly one song only, and does not sing other songs. Moreover, in order to make singing voice more beautiful, for every song, the following conditions should be satisfied.

• At least one beaver sings the song.
• The number of beavers singing the alto part of the song is equal to the number of beavers singing the bass part of the song.
• If we consider the beavers singing the song only, every alto beaver stands the stage right of every bass beaver.

Bitaro, the conductor, tried to find a way to allot songs to beavers which satisfies the conditions. Since Bitaro is bright, he notices that it might be impossible to allot songs to beavers.

In order to cope with this issue, Bitaro will perform the following operation several times so that there is a way to allot songs to beavers which satisfies the conditions.

• Swap the position of two adjacent beavers.

Since Bitaro thinks efficiency is important, he wants to minimize the number of operations. However, it turns out to be a surprisingly difficult problem. Since you are a brilliant programmer, Bitaro asks you to solve this problem.

Write a program which, given information of the chorus and the number of songs $K$, calculates the minimum number of operations Bitaro needs to perform. Note that, under the constraints of this task, it is possible to perform the operations several times so that there is a way to allot songs to beavers which satisfies the conditions.

输入格式

Read the following data from the standard input.

$N\ K$

$S$

输出格式

Write one line to the standard output. The output should contain the minimum number of operations Bitaro needs to perform.

题目大意

题目描述

在舞台上，有 $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】

In this sample input, for example, Bitaro can perform the following operations. Here, the underline denotes the positions of the two beavers swapped by Bitaro.

1. Swap the third beaver and the fourth beaver from the stage right.
   After this operation, the string which denotes the parts of the beavers from the stage right becomes $\text{`\texttt{AA\underline{AB}BABBAB}'}$.
2. Swap the eighth beaver and the ninth beaver from the stage right.
   After this operation, the string which denotes the parts of the beavers from the stage right becomes $\text{`\texttt{AAABBAB\underline{AB}B}'}$.

After these operations, Bitaro can allot songs to beavers as follows.

• From the stage right, the $1, 2, 3, 4, 5, 7$-th beavers sing the first song.
• From the stage right, the $6, 8, 9, 10$-th beavers sing the second song.

This way to allot songs to beavers satisfies the conditions.

If the number of operations is less than $2$, there does not exist a way to allot songs to beavers which satisfies the conditions. Therefore, output $2$.

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

【样例解释 #2】

Without performing operations, Bitaro can allot songs to beavers as follows.

• From the stage right, the $1, 2, 3, 5$-th beavers sing the first song.
• From the stage right, the $4, 6, 7, 8$-th beavers sing the second song.
• From the stage right, the $9, 10$-th beavers sing the third song.

This way to allot songs to beavers satisfies the conditions. Therefore, output $0$.

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

【样例解释 #3】

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

【样例解释 #4】

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

【数据范围】

对于所有测试数据，满足 $1\le N\le 10^6$，$1\le K\le N$，$S$ 是一个长度为 $2N$ 的字符串，且在 $S$ 中，字母 $\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$	无