ICPC 문제 세트를 준비하는 악랄한 심사위원들은 재능 있는 참가자들이 문제를 AC(맞았습니다)하고 문제 세트를 AK(“all kill”, 전부 해결)하는 것을 보는 것에 지쳤습니다. 그들은 이에 너무 지친 나머지 AC나 AK가 부분 수열로 나타나는 모든 문자열을 싫어하게 되었습니다. 심사위원들은 A, C, K 문자로만 구성된 문자열 $s$를 발견했고, 이 부분 수열들을 파괴하기로 결심했습니다!

한 번의 연산으로 심사위원들은 문자열 $s$에서 인접한 두 문자를 교환할 수 있습니다. 더 정확히 말하면, 심사위원은 인덱스 $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 문자로만 구성됩니다.

두 번째 줄에는 심사위원이 수행할 수 있는 최대 교환 횟수인 정수 $M$ ($0 \le M \le 2 \cdot 10^9$)이 주어집니다.

출력

최대 $M$번의 교환 연산을 최적으로 수행한 후 $s$에 남아 있는 AC 및 AK 부분 수열의 총 개수를 최소화하여 출력하십시오.

참고

예제 1에서, 문자열 $s$는 처음에 7개의 서로 다른 AC 부분 수열과 4개의 서로 다른 AK 부분 수열을 가지고 있습니다. 5번의 교환을 최적으로 수행하면 새로운 문자열 ACCCAAKA가 되며, 여기에는 3개의 AC 부분 수열과 3개의 AK 부분 수열만 남게 됩니다.

예제

입력 1

ACAACCAK
5

출력 1

6

입력 2

CCKKAKCKCK
1000000000

출력 2

0

입력 3

AAAAAAAAACCCCCCCCC
13

출력 3

68