Les juges malveillants qui préparent les jeux de problèmes de l'ICPC sont fatigués de voir les candidats talentueux réussir (« AC ») leurs problèmes et réussir tout le jeu de problèmes (« AK »). Ils en ont tellement assez qu'ils ont commencé à détester toute chaîne où AC ou AK apparaissent en tant que sous-séquences. Les juges viennent de trouver une chaîne $s$ composée uniquement des caractères A, C et K et sont déterminés à détruire ces sous-séquences !

En une opération, les juges peuvent échanger deux caractères adjacents dans la chaîne $s$. Pour être plus précis, les juges peuvent choisir un indice $i$ ($1 \le i < |s|$) et échanger $s_i$ et $s_{i+1}$. Les juges sont très occupés et n'ont pas beaucoup de temps, ils ne peuvent donc effectuer cette opération qu'au maximum $M$ fois (en choisissant indépendamment un indice $i$ à chaque fois).

L'objectif des juges est de minimiser le nombre de sous-séquences (éventuellement non contiguës) qui sont AC ou AK. Aidez-les à calculer le nombre de sous-séquences AC et AK qui restent dans $s$ après que les juges ont effectué une séquence optimale d'au plus $M$ opérations d'échange.

Entrée

La première ligne de l'entrée contient la chaîne $s$ ($1 \le |s| \le 2 \cdot 10^5$). La chaîne est composée uniquement des caractères A, C et K.

La deuxième ligne contient un entier $M$ ($0 \le M \le 2 \cdot 10^9$), le nombre maximum d'échanges que les juges peuvent effectuer.

Sortie

Affichez le nombre total minimum de sous-séquences AC et AK qui restent dans $s$ après une séquence optimale d'au plus $M$ opérations d'échange.

Remarque

Dans l'exemple 1, la chaîne $s$ possède initialement sept sous-séquences AC différentes et quatre sous-séquences AK différentes. Un choix optimal de cinq échanges donne la nouvelle chaîne ACCCAAKA qui ne possède plus que trois sous-séquences AC et trois sous-séquences AK.

Exemples

Entrée 1

ACAACCAK
5

Sortie 1

6

Entrée 2

CCKKAKCKCK
1000000000

Sortie 2

0

Entrée 3

AAAAAAAAACCCCCCCCC
13

Sortie 3

68