Moortal Cowmbat

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const ll N = 1e5 + 9;
const ll Alpha = 30;
const ll INF = 1e17;

ll dp[N][Alpha], A[Alpha][Alpha], dist[Alpha][Alpha], prefixDist[N][Alpha], minDP[N];
ll n, m, k;
string s;

int main () {
    freopen ("cowmbat.in", "r", stdin);
    freopen ("cowmbat.out", "w", stdout);
    cin >> n >> m >> k >> s;
    for (ll i = 0; i < m; i++)
        for (ll j = 0; j < m; j++)
            cin >> A[i][j];
    for (ll i = 0; i < m; i++)
        for (ll j = 0; j < m; j++)
            dist[i][j] = A[i][j];
    for (ll k = 0; k < m; k++)
        for (ll i = 0; i < m; i++)
            for (ll j = 0; j < m; j++)
                dist[i][j] = min (dist[i][j], dist[i][k] + dist[k][j]);
    for (ll j = 0; j < m; j++)
        prefixDist[0][j] = dist[s[0] - 'a'][j];
    for (ll i = 1; i < n; i++)
        for (ll j = 0; j < m; j++)
            prefixDist[i][j] = prefixDist[i - 1][j] + dist[s[i] - 'a'][j];
    for (ll i = 0; i < n; i++)
        minDP[i] = INF;
    for (ll j = 0; j < m; j++) {
        dp[k - 1][j] = prefixDist[k - 1][j];
        minDP[k - 1] = min (minDP[k - 1], dp[k - 1][j]);
    }
    for (ll i = k; i < n; i++) {
        for (ll j = 0; j < m; j++) {
            dp[i][j] = dp[i - 1][j] + dist[s[i] - 'a'][j];
            if (minDP[i - k] != INF)
                dp[i][j] = min (dp[i][j], prefixDist[i][j] - prefixDist[i - k][j] + minDP[i - k]);
            minDP[i] = min (minDP[i], dp[i][j]);
        }
    }
    cout << minDP[n - 1] << "\n";
    return 0;
}