负责准备 ICPC 题目集的邪恶评委们已经厌倦了看到天才选手们 AC 他们的题目，并 AK（“全杀”）他们的题集。他们对此感到非常厌烦，以至于开始讨厌任何包含 AC 或 AK 子序列的字符串。评委们刚刚发现了一个仅由字符 A、C 和 K 组成的字符串 $s$，并决心消灭这些子序列！

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

评委们的目标是最小化字符串中作为 AC 或 AK 的子序列（可能是不连续的）的数量。请帮助他们计算在执行最多 $M$ 次最优交换操作后，字符串 $s$ 中剩余的 AC 和 AK 子序列的总数。

输入格式

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

第二行包含一个整数 $M$ ($0 \le M \le 2 \cdot 10^9$)，即评委们可以执行的最大交换次数。

输出格式

输出在执行最多 $M$ 次最优交换操作后，字符串 $s$ 中剩余的 AC 和 AK 子序列的最小总数。

说明

在样例 1 中，字符串 $s$ 最初有 7 个不同的 AC 子序列和 4 个不同的 AK 子序列。一种最优的 5 次交换选择会产生新字符串 ACCCAAKA，其中仅剩下 3 个 AC 子序列和 3 个 AK 子序列。

样例

输入 1

ACAACCAK
5

输出 1

6

输入 2

CCKKAKCKCK
1000000000

输出 2

0

输入 3

AAAAAAAAACCCCCCCCC
13

输出 3

68