Злые судьи, готовящие комплекты задач для ICPC, устали видеть, как талантливые участники решают их задачи (AC) и полностью справляются с комплектами (AK — «all kill»). Они настолько устали от этого, что начали испытывать неприязнь к любым строкам, в которых AC или AK встречаются в качестве подпоследовательностей. Судьи только что нашли строку $s$, состоящую только из символов A, C и K, и полны решимости уничтожить эти подпоследовательности!

За одну операцию судьи могут поменять местами два соседних символа в строке $s$. Точнее, судьи могут выбрать индекс $i$ ($1 \le i < |s|$) и поменять местами $s_i$ и $s_{i+1}$. Судьи очень заняты и у них мало времени, поэтому они могут выполнить эту операцию не более $M$ раз (каждый раз независимо выбирая индекс $i$).

Цель судей — минимизировать количество подпоследовательностей (возможно, не являющихся непрерывными), которые образуют AC или AK. Помогите им вычислить количество подпоследовательностей AC и AK, которые останутся в строке $s$ после того, как судьи выполнят оптимальную последовательность из не более чем $M$ операций обмена.

Входные данные

Первая строка содержит строку $s$ ($1 \le |s| \le 2 \cdot 10^5$). Строка состоит только из символов A, C и K.

Вторая строка содержит целое число $M$ ($0 \le M \le 2 \cdot 10^9$), максимальное количество обменов, которые могут выполнить судьи.

Выходные данные

Выведите минимальное суммарное количество подпоследовательностей AC и AK, которые останутся в строке $s$ после выполнения оптимальной последовательности из не более чем $M$ операций обмена.

Примечание

В первом примере строка $s$ изначально содержит семь различных подпоследовательностей AC и четыре различные подпоследовательности AK. Один из оптимальных вариантов из пяти обменов дает новую строку ACCCAAKA, в которой осталось только три подпоследовательности AC и три подпоследовательности AK.

Примеры

Пример 1

ACAACCAK
5

6

Пример 2

CCKKAKCKCK
1000000000

0

Пример 3

AAAAAAAAACCCCCCCCC
13

68