1559. Elective System

/********************
* Problem: -.
* Theme: Ukrainian 3 stage 2017 - 1
*/
#include <bits/stdc++.h>

using namespace std;

#define int long long
#define mp make_pair
#define pb push_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define RFOR(i,a,b) for(int i=(a);i>=(b);i--)
#define SZ(A) A.size()
#define f first
#define s second

typedef vector<int> VI;
typedef vector<pair<int,int> > VII;
typedef pair<int,int> pii;
typedef pair<int,pair<int,int> > pip;
typedef pair<pair<int,int>,pair<int,int> > ppp;
typedef pair<pair<int,int>,int> ppi;

const long double PI = acos(-1);
const int INF = (int)1e18;
const int MOD = (int)1e9+7;
const int N = 100001;

int d,k;

void solve_case()
{
    string s;
    cin >> s;

    int n = s.size();

    int dp[k+1][n+1];
    for(int i=0;i<n;i++)
        dp[0][i] = 0;

    vector<int> preff(n+1,0);

    preff[0] = 0;

    for(int i=1;i<=n;i++)
        preff[i] = preff[i-1] + s[i-1] - 'a' + 1;

    if(d * k >= n)
    {
        cout << preff[n] << "\n";
        return;
    }

//    cerr << "WOW";

    for(int j=1;j<=k;j++)
    {
        for(int i=0;i<=n;i++)
        {
            if(i < d)
                dp[j][i] = dp[j-1][i];
            else
                dp[j][i] = max(dp[j-1][i-d] + preff[i] - preff[i-d], dp[j][i-1]);
        }
    }

    cout << dp[k][n] << '\n';

    return;
}

signed main()
{
//    ios::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr);
//    freopen("input.txt","r",stdin);
//    freopen("output.txt","w",stdout);

    int t = 1;
//    cin >> t;

    while(cin >> d >> k)
    {
        solve_case();
    }

    return 0;
}

/*

t*(t+1)/2 == n

t^2 + t - n == 0

D=1+4*n

x1 = (sqrt(D)+1)/2

0 1 1 2 1 2 2 3 1  2  2  3  2  3  3  4

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

0 1 2 3 4 5 6 7 8  9 10 11 12 13 14 15
*/