#include<cstdio>
#include<iostream>
#include<utility>
using namespace std;
const int o=1e6+10;const long long inf=2e18;
int n,K,a[o],bnd[o],q[o],b[o],hd,tl,cnt,v[o];long long sm[o];pair<long long,int> f[o];char s[o*2];
inline long long calc(int l,int r){
	int t=max(l+1,bnd[l]);
	if(t<=r) return sm[r]-sm[t-1]-l*(r-t+1ll);
	return 0;
} 
inline pair<long long,int> add(pair<long long,int> pr,long long v){return make_pair(pr.first+v,pr.second);}
inline int fnd(int x,int y){
	if(Y[x]==y) return v[x];
	Y[x]=y;
	if(add(f[x],calc(x,n))<add(f[y],calc(y,n))) return v[x]=n+1;
	int l=y,r=n,md;
	for(;l<r;){
		md=l+r>>1;
		if(add(f[x],calc(x,md))>=add(f[y],calc(y,md))) r=md;
		else l=md+1;
	}
	return v[x]=l;
}
inline void slv(long long val){
	q[hd=tl=1]=0;
	for(int i=0;i<=n;++i) Y[i]=-1;
	for(int i=1;i<=n;++i){
		for(;hd<tl&&b[hd]<=i;++hd);
		f[i]=add(f[q[hd]],calc(q[hd],i)+val);++f[i].second;
		for(;hd<tl&&b[tl-1]>=fnd(q[tl],i);--tl);
		q[++tl]=i;b[tl-1]=fnd(q[tl-1],q[tl]);
	}
}
int main(){
	scanf("%d%d%s",&n,&K,s+1);
	for(int i=1,j=0,t=0;i<=n*2;++i)
		if(s[i]=='A') a[++j]=t;
		else ++t;
	for(int i=1;i<=n;++i) sm[i]=sm[i-1]+a[i];
	for(int i=0;i<n;++i) bnd[i]=lower_bound(a,a+n+1,i)-a;
	for(long long l=0,r=n*1ll*n,md;1;){
		if(l==r){slv(l);printf("%lld",f[n].first-K*l);break;}
		slv(md=l+r>>1);
		if(f[n].second<=K) r=md;
		else l=md+1;
	}
	return 0;
}

answer.code: In function ‘int fnd(int, int)’:
answer.code:14:12: error: ‘Y’ was not declared in this scope
   14 |         if(Y[x]==y) return v[x];
      |            ^
answer.code:15:9: error: ‘Y’ was not declared in this scope
   15 |         Y[x]=y;
      |         ^
answer.code: In function ‘void slv(long long int)’:
answer.code:27:31: error: ‘Y’ was not declared in this scope
   27 |         for(int i=0;i<=n;++i) Y[i]=-1;
      |                               ^
answer.code: In function ‘int main()’:
answer.code:36:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   36 |         scanf("%d%d%s",&n,&K,s+1);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~