Các giám khảo độc ác chuẩn bị bộ đề thi ICPC đã quá mệt mỏi khi thấy các thí sinh tài năng liên tục AC các bài toán và AK ("all kill" - giải hết) các bộ đề thi của họ. Họ đã chán ngấy đến mức bắt đầu ghét bất kỳ xâu nào có AC hoặc AK xuất hiện dưới dạng các dãy con. Các giám khảo vừa tìm thấy một xâu $s$ chỉ gồm các ký tự A, C và K và quyết tâm tiêu diệt các dãy con này!

Trong một thao tác, các giám khảo có thể hoán đổi hai ký tự kề nhau trong xâu $s$. Cụ thể hơn, các giám khảo có thể chọn một chỉ số $i$ ($1 \le i < |s|$) và hoán đổi $s_i$ và $s_{i+1}$. Các giám khảo rất bận rộn và không có nhiều thời gian, vì vậy họ chỉ có thể thực hiện thao tác này tối đa $M$ lần (mỗi lần chọn chỉ số $i$ một cách độc lập).

Mục tiêu của các giám khảo là giảm thiểu số lượng các dãy con (có thể không liên tiếp) là AC hoặc AK. Hãy giúp họ tính toán số lượng dãy con AC và AK còn lại trong $s$ sau khi các giám khảo thực hiện một chuỗi thao tác hoán đổi tối ưu với tối đa $M$ lần.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa xâu $s$ ($1 \le |s| \le 2 \cdot 10^5$). Xâu chỉ bao gồm các ký tự A, C và K.

Dòng thứ hai chứa một số nguyên $M$ ($0 \le M \le 2 \cdot 10^9$), số lần hoán đổi tối đa mà các giám khảo có thể thực hiện.

Dữ liệu ra

In ra số lượng tối thiểu các dãy con AC và AK còn lại trong $s$ sau một chuỗi thao tác hoán đổi tối ưu với tối đa $M$ lần.

Ghi chú

Trong Ví dụ 1, xâu $s$ ban đầu có bảy dãy con AC khác nhau và bốn dãy con AK khác nhau. Một lựa chọn tối ưu gồm năm lần hoán đổi tạo ra xâu mới ACCCAAKA, trong đó chỉ còn lại ba dãy con AC và ba dãy con AK.

Ví dụ