#include <iostream> #include <bits/stdc++.h> #define ll long long using namespace std; const ll maxn = 2*1e5+5, INF = 4e18+9; void solve(){ int N, K; cin >> N >> K; string s; cin >> s; s = ' ' + s; int j = 1; bool skip = false; ll EX = 0; for(int i = 1; i <= N*2; i++){ if(skip){ skip = false; continue; } if(s[i] == 'A') continue; while(s[j] == 'B'){ j++; } assert(j <= N*2); if(j > i){ EX += j-i; swap(s[i], s[j]); skip = true; } j++; } int it = -1; ll poss = 0, owe = 0, cur = 0; vector<ll> sump(1), X(1), cnt(1); for(int i = 1; i <= N*2; i++){ if(s[i] == 'A'){ cur++; it++; poss += i - it; }else{ if(owe > 0){ owe--; }else{ sump.push_back(poss); X.push_back(i); cnt.push_back(cur); owe = cur-1; cur = 0; poss = 0; } } } int n = X.size()-1; vector<ll> pfsp(n+1, 0), pfcnt(n+1, 0); for(int i = 1; i <= n; i++){ pfsp[i] = pfsp[i-1] + sump[i]; pfcnt[i] = pfcnt[i-1] + cnt[i]; } //lets do subtask n <= 500 first! if(n <= K){ cout << EX; return; } vector<vector<ll>> f(n+1, vector<ll>(K+1, INF)); f[0][0] = 0; for(int i = 1; i <= n; i++){ for(int j = 1; j <= K; j++){ for(int p = 1; p <= i; p++){ ll cost = pfsp[i]-pfsp[p] - (pfcnt[i]-pfcnt[p])*X[p] + pfcnt[p]*(pfcnt[i]-pfcnt[p]); f[i][j] = min(f[i][j], f[p-1][j-1] + cost); } } } cout << f[n][K] + EX; } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); solve(); }