Translated Document to Fix
Los jueces malvados que preparan los conjuntos de problemas de la ICPC están cansados de ver a los talentosos concursantes hacer AC en sus problemas y AK ("all kill") en sus conjuntos de problemas. Se han cansado tanto de esto que han empezado a detestar cualquier cadena donde AC o AK aparezcan como subsecuencias. ¡Los jueces acaban de encontrar una cadena $s$ que consiste solo en los caracteres A, C y K y están decididos a destruir estas subsecuencias!
En una operación, los jueces pueden intercambiar dos caracteres adyacentes en la cadena $s$. Para ser más precisos, los jueces pueden elegir un índice $i$ ($1 \le i < |s|$) e intercambiar $s_i$ y $s_{i+1}$. Los jueces están muy ocupados y no tienen mucho tiempo, por lo que solo pueden realizar esta operación hasta $M$ veces (eligiendo un índice $i$ de forma independiente cada vez).
El objetivo de los jueces es minimizar el número de subsecuencias (posiblemente no contiguas) que sean AC o AK. Ayúdales a calcular el número de subsecuencias AC y AK que permanecen dentro de $s$ después de que los jueces realicen una secuencia óptima de hasta $M$ operaciones de intercambio.
Entrada
La primera línea de la entrada contiene la cadena $s$ ($1 \le |s| \le 2 \cdot 10^5$). La cadena consiste únicamente en los caracteres A, C y K.
La segunda línea contiene un entero $M$ ($0 \le M \le 2 \cdot 10^9$), el número máximo de intercambios que los jueces pueden realizar.
Salida
Imprime el número total mínimo de subsecuencias AC y AK que permanecen en $s$ después de una secuencia óptima de hasta $M$ operaciones de intercambio.
Nota
En el Ejemplo 1, la cadena $s$ inicialmente tiene siete subsecuencias AC diferentes y cuatro subsecuencias AK diferentes. Una elección óptima de cinco intercambios produce la nueva cadena ACCCAAKA, la cual solo tiene tres subsecuencias AC y tres subsecuencias AK restantes, para un total de 6.
Ejemplos
Entrada 1
ACAACCAK 5
Salida 1
6
Entrada 2
CCKKAKCKCK 1000000000
Salida 2
0
Entrada 3
AAAAAAAAACCCCCCCCC 13
Salida 3
68