Zli sędziowie przygotowujący zestawy zadań ICPC są zmęczeni widokiem utalentowanych zawodników, którzy rozwiązują ich zadania (AC) i zaliczają cały zestaw (AK – „all kill”). Zmęczyło ich to do tego stopnia, że zaczęli nie lubić wszelkich ciągów, w których AC lub AK występują jako podciągi. Sędziowie właśnie znaleźli ciąg $s$ składający się wyłącznie ze znaków A, C oraz K i są zdeterminowani, aby zniszczyć te podciągi!

W jednej operacji sędziowie mogą zamienić miejscami dwa sąsiednie znaki w ciągu $s$. Mówiąc dokładniej, sędziowie mogą wybrać indeks $i$ ($1 \le i < |s|$) i zamienić $s_i$ oraz $s_{i+1}$. Sędziowie są bardzo zajęci i nie mają zbyt wiele czasu, więc mogą wykonać tę operację maksymalnie $M$ razy (za każdym razem niezależnie wybierając indeks $i$).

Celem sędziów jest zminimalizowanie liczby podciągów (niekoniecznie spójnych), które są równe AC lub AK. Pomóż im obliczyć liczbę podciągów AC oraz AK, które pozostaną w ciągu $s$ po wykonaniu przez sędziów optymalnej sekwencji co najwyżej $M$ operacji zamiany.

Wejście

Pierwsza linia wejścia zawiera ciąg $s$ ($1 \le |s| \le 2 \cdot 10^5$). Ciąg składa się wyłącznie ze znaków A, C oraz K.

Druga linia zawiera liczbę całkowitą $M$ ($0 \le M \le 2 \cdot 10^9$), maksymalną liczbę zamian, jakie mogą wykonać sędziowie.

Wyjście

Wypisz minimalną łączną liczbę podciągów AC oraz AK, które pozostaną w ciągu $s$ po wykonaniu optymalnej sekwencji co najwyżej $M$ operacji zamiany.

Uwagi

W pierwszym przykładzie ciąg $s$ początkowo zawiera siedem różnych podciągów AC oraz cztery różne podciągi AK. Jeden z optymalnych wyborów pięciu zamian prowadzi do nowego ciągu ACCCAAKA, w którym pozostały tylko trzy podciągi AC oraz trzy podciągi AK.

Przykład

Wejście 1

ACAACCAK
5

Wyjście 1

6

Wejście 2

CCKKAKCKCK
1000000000

Wyjście 2

0

Wejście 3

AAAAAAAAACCCCCCCCC
13

Wyjście 3

68