舞台上，$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 最少需要进行的操作次数。

样例输入 1

5 2
AABABABBAB

样例输出 1

2

在这组样例中，Bitaro 可以进行如下操作。这里，下划线部分表示 Bitaro 交换了这两只河狸的位置。

1. 交换从舞台右侧数第三只和第四只河狸
   在这次操作后，从舞台右侧表示河狸的字符串变为 $\mathtt{\text{AA}}\underset{―}{\mathtt{\text{AB}}}\mathtt{\text{BABBAB}}$

2. 交换从舞台右侧数第八只和第九只河狸
   在这次操作后，从舞台右侧表示河狸的字符串变为 $\mathtt{\text{AAABBAB}}\underset{―}{\mathtt{\text{AB}}}\mathtt{\text{B}}$

在这些操作后，Bitaro 可以按如下方式给河狸分配歌曲。

• 从舞台右侧，第 $1,2,3,4,5,7$ 只河狸唱第一首歌
• 从舞台右侧，第 $6,8,9,10$ 只河狸唱第二首歌

这种分配歌曲的方式满足条件。

如果操作次数小于 $2$，则不存在一种分配歌曲的方式使得满足条件。因此输出 $2$。

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

这组样例满足子任务 $1,2,4,5,6,7$ 的限制。

样例输入 2

5 3
AABABABBAB

样例输出 2

0

不进行操作，Bitaro 可以按如下方式分配歌曲。

• 从舞台右侧，第 $1,2,3,5$ 只河狸唱第一首歌
• 从舞台右侧，第 $4,6,7,8$ 只河狸唱第二首歌
• 从舞台右侧，第 $9,10$ 只河狸唱第三首歌

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

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

样例输入 3

3 1
BBBAAA

样例输出 3

9

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

样例输入 4

10 3
ABABBBBABBABABABAAAA

样例输出 4

37

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

数据范围

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

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

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

时间限制：6s

空间限制：1024 MB