SPOJ DINNER_DINGRP/ DP

/***
 created: 2022-07-19-22.23.24
***/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename U> using ordered_set=tree<U, null_type,less<U>,rb_tree_tag,tree_order_statistics_node_update>;
#define ll long long
#define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
#define get_lost_idiot return 0
#define nl '\n'

ll dp[105][105][105],n,m;

string a;

ll solve(ll i,ll j,ll cnt)
{
    if(i>j || i>n || j<0) return 0;

    if(dp[i][j][cnt]!=-1) return dp[i][j][cnt];

    ll ans=INT_MAX;

    if(cnt>=m) ans = 1 + solve(i+1,j,1);

    for(ll k=i+1;k<=j;k++)
    {
        if(a[i]==a[k])
        {
            ans=min(ans,solve(i+1,k-1,1)+solve(k,j,cnt+1));
            //ans=min(ans,solve(i+1,j-1,1)+solve(k,j,cnt+1));
            //ans=min(ans,solve(i+1,j-1,1)+solve(k+1,j,cnt+1));
        }
    }

    return dp[i][j][cnt]=ans;
}


int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);


    ll i,j,k,l;

    cin>>n>>m;

    cin>>a;

    memset(dp,-1,sizeof dp);

    l=solve(0,n-1,1);

    // cout<<l<<nl;

    if(l>n) cout<<-1<<nl;
    else cout<<l<<nl;

    get_lost_idiot;
}