You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

草莓之歌(easy)

题目描述

在草莓国，每年都要举办演唱草莓歌的大型活动。

舞台上，$2N$ 名演出者排成一排。草莓歌有两个声部：红草莓声部和金草莓声部。每一名演出者只能唱一种声部。这个信息用一个字符串 $S$ 给出。具体地，对于从舞台的左边起第 $i$ 名演出者，如果字符串 $S$ 中第 $i$ 个字符为 $\texttt{A}$，则这名演出者唱红草莓声部；如果为 $\texttt{B}$，则唱金草莓声部。保证字符串 $S$ 中恰有 $N$ 个 $\texttt{A}$ 和 $\texttt{B}$。

现在开始，演出者们要唱 $K$ 首草莓歌。然而因为草莓歌十分消耗体力，所以每名演出者只能恰好唱一首草莓歌。并且为了表示对草莓的崇拜，对于每首草莓歌都应满足以下条件：

• 至少一名演出者唱这首歌
• 唱红草莓声部的演出者的数量等于唱金草莓声部的演出者的数量
• 如果只考虑唱这首歌的演出者，则每名唱红草莓声部的演出者在舞台上都站在所有唱金草莓声部的演出者的左边

Madeline 导演要找到一种给每名演出者分配歌曲的方式，但目前可能并不存在一种合法的方案。

但是 Madeline 会使用名为 Wave Dash 的魔法。每使用一次魔法，Madeline 可以选择两名相邻的演出者，将他们交换。请你求出最少使用几次魔法，使得存在一种合法的分配方案。

输入格式

从 easy.in 中读入数据。

第一行两个整数 $N$ 和 $K$。

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

输出格式

输出到 easy.out 中。

一行一个整数，代表答案。

输入输出样例

5 3
AABABABBAB

0

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$ 个字符 $\texttt{A}$ 和 $N$ 个字符 $\texttt{B}$