舞台上站着 $2N$ 只海狸，它们是合唱团的成员。每只海狸要么演唱合唱团的男高音部分，要么演唱男低音部分。这些信息由字符串 $S$ 给出。具体来说，从舞台右侧（即从观众席看去的左侧）数起的第 $i$ 只海狸（$1 \le i \le 2N$），如果 $S$ 的第 $i$ 个字符是 'A'，则演唱男高音部分；如果 $S$ 的第 $i$ 个字符是 'B'，则演唱男低音部分。共有 $N$ 只海狸演唱男高音，有 $N$ 只海狸演唱男低音。

现在，海狸们将演唱 $K$ 首歌曲。由于所有歌曲都非常困难，每只海狸只演唱一首歌曲，且不演唱其他歌曲。此外，为了使歌声更优美，每首歌曲都必须满足以下条件：

• 至少有一只海狸演唱该歌曲。
• 演唱该歌曲的男高音海狸数量等于演唱该歌曲的男低音海狸数量。
• 仅考虑演唱该歌曲的海狸，每一只男高音海狸都站在每一只男低音海狸的舞台右侧。

指挥家 Bitaro 试图找到一种满足上述条件的歌曲分配方式。由于 Bitaro 很聪明，他注意到可能无法将歌曲分配给海狸。

为了解决这个问题，Bitaro 将执行多次以下操作，以便存在一种满足条件的歌曲分配方式：

• 交换两只相邻海狸的位置。

由于 Bitaro 认为效率很重要，他希望最小化操作次数。然而，这被证明是一个非常困难的问题。作为一名优秀的程序员，Bitaro 请你解决这个问题。

编写一个程序，给定合唱团的信息和歌曲数量 $K$，计算 Bitaro 需要执行的最小操作次数。注意，在本任务的约束条件下，可以通过多次执行操作，使得存在一种满足条件的歌曲分配方式。

输入格式

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

$N \ K$ $S$

输出格式

将结果输出到标准输出。输出应包含 Bitaro 需要执行的最小操作次数。

数据范围

• $1 \le N \le 1\,000\,000$
• $1 \le K \le N$
• $S$ 是一个长度为 $2N$ 的字符串。在字符串 $S$ 中，字符 'A' 出现 $N$ 次，字符 'B' 出现 $N$ 次。
• $N, K$ 为整数。

子任务

1. (16 分) $N \le 10$
2. (24 分) $N \le 500$
3. (21 分) $N \le 5\,000$
4. (26 分) $N \le 100\,000$
5. (13 分) 无附加约束。

样例

样例输入 1

5 2
AABABABBAB

样例输出 1

2

样例输入 2

5 3
AABABABBAB

样例输出 2

0

样例输入 3

3 1
BBBAAA

样例输出 3

9

样例输入 4

10 3
ABABBBBABBABABABAAAA

样例输出 4

37