说明

准备 ICPC 题目的邪恶出题人们，厌倦了看到才华横溢的参赛选手 AC 题目并 AK（“全部杀死”）整套题目。他们已经对此深感厌倦，以至于开始讨厌任何将 $\texttt{AC}$ 或 $\texttt{AK}$ 作为子序列出现的字符串。出题人们刚刚发现了一个仅由字符 $\texttt{A}$、$\texttt{C}$ 和 $\texttt{K}$ 组成的字符串 $s$，并决心摧毁这些子序列！

在一次操作中，出题人可以交换字符串 $s$ 中两个相邻的字符。更准确地说，出题人可以选择一个下标 $i$（$1 \le i < |s|$），并交换 $s_i$ 和 $s_{i+1}$。出题人非常忙碌，时间有限，因此他们最多只能进行 $M$ 次这样的操作（每次独立地选择一个下标 $i$）。

出题人的目标是尽量减少是 $\texttt{AC}$ 或 $\texttt{AK}$ 的子序列（可能不连续）的数量。请帮助他们在最多 $M$ 次交换操作的最优序列后，计算出字符串 $s$ 中剩余的 $\texttt{AC}$ 和 $\texttt{AK}$ 子序列的数量。

输入格式

输入的第一行包含字符串 $s$ $(1 \leq |s| \leq 2\cdot 10^5)$。该字符串仅由字符 $\texttt{A}$、$\texttt{C}$ 和 $\texttt{K}$ 组成。

第二行包含一个整数 $M$ $(0 \leq M \leq 2\cdot 10^9)$，表示出题人最多可以执行的交换次数。

输出格式

输出一个整数，表示在经过最多 $M$ 次交换操作的最优序列后，字符串 $s$ 中剩余的 $\texttt{AC}$ 和 $\texttt{AK}$ 子序列的最小总数。

ACAACCAK
5

6

CCKKAKCKCK
1000000000

0

AAAAAAAAACCCCCCCCC
13

68

提示

样例输入 1 解释

在样例输入 1 中，初始字符串 $s$ 有 $7$ 个不同的 $\texttt{AC}$ 子序列和 $4$ 个不同的 $\texttt{AK}$ 子序列。一种最优的五次交换方案得到新字符串 $\texttt{ACCCAAKA}$，其中只剩下 $3$ 个 $\texttt{AC}$ 子序列和 $3$ 个 $\texttt{AK}$ 子序列。

翻译由 DeepSeek V3.2 完成