#include<bits/stdc++.h>
using namespace std ;
#define maxn 200009
#define ll long long
#define fi first
#define se second
#define pb push_back
#define left id<<1
#define right id<<1|1
#define re exit(0);
const int mod = 1e9+7 ;
const int INF = 1e9 ;
const int LOG = 18 ;
typedef vector<int> vi ;
typedef vector<ll> vl ;
typedef pair<int,int> pii ;
typedef vector<pii> vii ;
typedef pair<ll,ll> pll ;
void add ( int &a , int b )
{
a += b ;
if ( a < 0 ) a += mod ;
if ( a >= mod ) a -= mod ;
}
template < typename T > void chkmin (T &a , T b) { if (a>b) a=b ;}
template < typename T > void chkmax (T &a , T b) { if (a<b) a=b ;}
void rf ()
{
freopen ("bai1.inp","r",stdin) ;
// freopen ("bai1.out","w",stdout) ;
}
int _pow ( int a , int n )
{
if ( n == 0 ) return 1 ;
int res = _pow(a,n/2) ;
if ( n % 2 ) return (1ll*res*res%mod*a%mod) ;
else return 1ll*res*res%mod ;
}
int n , k ;
int a [maxn] ;
int b [maxn] ;
int res = 0 ;
void init_array ()
{
int deg = 0 , cnt = 0 , num = 0 ;
for ( int i = 1 ; i <= n*2 ; i ++ )
{
if ( a [i] == 0 )
{
b [++num] = a [i] ; deg ++ ; res += cnt ;
if ( cnt > 0 && deg > 0 ) b [++num] = 1 , cnt -- , deg -- ;
}
else
{
if ( deg > 0 ) b [++num] = a [i] , deg -- ;
else cnt ++ ;
}
}
while ( cnt > 0 ) b[++num] = 1 , cnt -- ;
}
int point [5009][5009] ;
int sum [5009][5009] ;
int dp [5009][5009] ;
void build_cost ()
{
int x = 0 , y = 0 ;
for ( int i = 1 ; i <= n*2 ; i ++ )
{
if ( b [i] ) y ++ ;
else
{
for ( int r = 0 ; r <= y ; r ++ ) point [x][r] = 1 ;
x ++ ;
}
}
for ( int i = 0 ; i <= n ; i ++ )
{
for ( int j = n ; j >= 0 ; j -- )
{
sum [i][j] = sum [i][j+1] + point [i][j] ;
if ( i > 0 ) sum [i][j] = sum [i][j] + sum [i-1][j] - sum [i-1][j+1] ;
}
}
}
int get_cost ( int l , int r )
{
if ( l == r ) return 0 ;
if ( l+1 == r ) return 0 ;
return sum [r-1][l+1] ;
}
void sub1 ()
{
build_cost () ;
memset ( dp , 0x3f , sizeof dp ) ;
dp [0][0] = 0 ;
for ( int i = 1 ; i <= n ; i ++ )
{
for ( int j = 0 ; j < i ; j ++ )
{
int cost = sum [i-1][j+1] ;
if ( i == j+1 ) cost = 0 ;
for ( int t = 1 ; t <= k ; t ++ ) chkmin (dp[i][t],dp[j][t-1]+cost) ;
}
}
int Min = INF ;
for ( int i = 0 ; i <= k ; i ++ ) chkmin (Min,dp[n][i]) ;
cout << res + Min ;
}
void dnc ( int l , int r , int optl , int optr , int j )
{
if ( l > r ) return ;
int mid = (l+r)/2 ;
int opt ;
for ( int i = optl ; i <= min (optr,mid) ; i ++ )
{
if ( dp [mid][j] > dp [i][j-1] + get_cost (i,mid) )
{
dp [mid][j] = dp [i][j-1] + get_cost (i,mid) ;
opt = i ;
}
}
dnc (l,mid-1,optl,opt,j) ;
dnc (mid+1,r,opt,optr,j) ;
}
void sub2 ()
{
build_cost () ;
memset ( dp , 0x3f , sizeof dp ) ;
for ( int i = 1 ; i <= n ; i ++ ) dp [i][1] = get_cost (0,i) ;
for ( int i = 2 ; i <= k ; i ++ ) dnc (1,n,1,n,i) ;
int Min = INF ;
for ( int i = 0 ; i <= k ; i ++ ) chkmin (Min,dp[n][i]) ;
cout << res + Min ;
}
int main ()
{
ios_base::sync_with_stdio(0) ;
cin.tie(0) ; cout.tie(0) ;
// rf () ;
cin >> n >> k ;
for ( int i = 1 ; i <= n*2 ; i ++ )
{
char c ; cin >> c ;
a [i] = c - 'A' ;
}
init_array () ;
sub2 () ; re
if ( n <= 500 ) sub1 () ;
else sub2 () ;
}
