#pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> using namespace std; #define pb push_back #define all(a) a.begin(),a.end() typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef unsigned long long ull; typedef vector<int> vi; int dp[1001][501]; vector<int> A(1,0), B(1,0); int Cost(int j, int i){ int len = i-j, res = 0; for(int l = 1; l <= len/2; l++){ res += max(0,A[l+j/2] - j-l); } return res; } void solve(){ int n,k; cin >> n >> k; for(int i = 1; i <= 2*n; i++){ char c; cin >> c; if(c=='A') A.emplace_back(i); else B.emplace_back(i); } for(int i = 2; i <= 2*n; i+=2){ fill(dp[i],dp[i]+k+1,1e9); for(int j = 0; j < i; j+=2){ int c = Cost(j,i); for(int l = 1; l <= k; l++) dp[i][l] = min(dp[i][l],dp[j][l-1]+c); } } int ans = 1e9; for(int j = 1; j <= k; j++) ans = min(ans,dp[2*n][j]); cout << ans; } signed main(){ cin.tie(0)->sync_with_stdio(0); int t = 1; // cin >> t; while(t--){solve();} }