準備 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$ 最初有七個不同的 AC 子序列和四個不同的 AK 子序列。一種最佳的五次交換選擇會產生新字串 ACCCAAKA，其中僅剩下三個 AC 子序列和三個 AK 子序列。

範例

輸入 1

ACAACCAK
5

輸出 1

6

輸入 2

CCKKAKCKCK
1000000000

輸出 2

0

輸入 3

AAAAAAAAACCCCCCCCC
13

輸出 3

68