The evil judges preparing the ICPC problem sets are tired of seeing the talented contestants AC their problems and AK ("all kill") their problem sets. They have grown so tired of this that they've started to dislike any strings where or appear as subsequences. The judges just found a string consisting of only the characters , , and and are determined to destroy these subsequences!
In one operation, the judges are able to swap two adjacent characters in the string . To be more precise, the judges may choose an index () and swap and . The judges are very busy and don't have much time, so they can only do this operation up to times (independently choosing an index each time).
The judges' goal is to minimize the number of subsequences () that are or . Help them calculate the number of and subsequences that remain within after the judges perform an optimal sequence of up to swap operations.
输入格式
The first line of input contains the string . The string consists only of the characters , , and .
The second line contains an integer , the maximum number of swaps the judges can perform.
输出格式
Print the minimum total number of and subsequences that remain in after an optimal sequence of at most swap operations.
样例
样例输入 1
ACAACCAK
5
样例输出 1
6
样例输入 2
CCKKAKCKCK
1000000000
样例输出 2
0
样例输入 3
AAAAAAAAACCCCCCCCC
13
样例输出 3
68
数据范围与提示
Explanation of Sample Input 1
In Sample Input 1, the string initially has seven different subsequences and four different subsequences. One optimal choice of five swaps yields the new string which only has three subsequences and three subsequences left.
