ICPCの問題セットを作成する邪悪な審査員たちは、才能ある出場者が問題をAC（正解）し、問題セットをAK（全問正解）するのを見るのにうんざりしています。彼らはこれに非常にうんざりしており、AC または AK が部分列として現れる文字列を嫌うようになりました。審査員たちは、A、C、K の文字のみからなる文字列 $s$ を見つけ、これらの部分列を破壊しようと決意しました！

1回の操作で、審査員は文字列 $s$ 内の隣接する2つの文字を入れ替えることができます。より正確には、審査員はインデックス $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 の文字のみで構成されています。

2行目には、審査員が行うことができる最大入れ替え回数を示す整数 $M$ ($0 \le M \le 2 \cdot 10^9$) が含まれます。

出力

最大 $M$ 回の入れ替え操作を最適に行った後に、$s$ 内に残る AC および AK 部分列の合計数の最小値を出力してください。

入出力例

入力 1

ACAACCAK
5

出力 1

6

注記

サンプル入力1では、文字列 $s$ には最初、7つの異なる AC 部分列と4つの異なる AK 部分列が含まれています。5回の入れ替えを最適に行うと、新しい文字列 ACCAACKA が得られ、これには AC 部分列が3つ、AK 部分列が3つだけ残ります。

入力 2

CCKKAKCKCK
1000000000

出力 2

0

入力 3

AAAAAAAAACCCCCCCCC
13

出力 3

68