题目描述

题目译自 JOISC 2023 Day3 T1 「ビーバーの合唱 / Chorus」

舞台上，$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$。

第二行一个长为 $2N$ 的字符串 $S$。

输出格式

输出一行一个整数，表示 Bitaro 最少需要进行的操作次数。

5 2
AABABABBAB

2

5 3
AABABABBAB

0

3 1
BBBAAA

9

10 3
ABABBBBABBABABABAAAA

37

数据范围与提示

对于所有输入数据，满足：

• $1\le N\le 10^6$
• $1\le K\le N$
• $S$ 中包含 $N$ 个字符 A 和 $N$ 个字符 B

详细子任务附加限制及分值如下表所示。