Moortal Cowmbat

#include <bits/stdc++.h>
using namespace std;

const int OO = 1e9 + 1;

int main(){
    freopen("cowmbat.in", "r", stdin);
    freopen("cowmbat.out", "w", stdout);

    int nBoutons, nLettres, lenCombo;
    cin >> nBoutons >> nLettres >> lenCombo;

    vector<int> comboDep(nBoutons);
    for (int& valeur : comboDep){
        char lettre;
        cin >> lettre;

        valeur = lettre - 'a';
    }

    int minDelta[nLettres][nLettres];
    for (int iDep = 0; iDep < nLettres; ++iDep)
        for (int iFin = 0; iFin < nLettres; ++iFin)
            cin >> minDelta[iDep][iFin];

    //On fait un Floyd-Warshall pour connaitre les vrais min de deltas.
    for (int iTrans = 0; iTrans < nLettres; ++iTrans)
        for (int iDep = 0; iDep < nLettres; ++iDep)
            for (int iFin = 0; iFin < nLettres; ++iFin)
                minDelta[iDep][iFin] = min(minDelta[iDep][iFin], minDelta[iDep][iTrans] + minDelta[iTrans][iFin]);

    /*cout << "----\n";

    for (int i = 0; i < nLettres; ++i){
        for (int j = 0; j < nLettres; ++j)
            cout << minDelta[i][j] << " ";
        cout << endl;
    }
    cout << "----\n";*/
    int dp[nBoutons][nLettres][2]; //Dp[i][j] : Min cout pour que ce soit valable de 0 à i inclus où la couleur de i est j.
    int sum[nBoutons][nLettres]; //Sum[i][j] somme de 0 à i inclus des couts pour transformer tout en j

    for (int iLettre = 0; iLettre < nLettres; ++iLettre){
        int curValue = 0;
        for (int iFin = 0; iFin < nBoutons; ++iFin){
            curValue += minDelta[comboDep[iFin]][iLettre];
            sum[iFin][iLettre] = curValue;
        }
    }

    for (int i = 0; i < nBoutons; ++i)
        for (int j = 0; j < nLettres; ++j)
            dp[i][j][0] = dp[i][j][1] = OO;

    for (int iFin = lenCombo - 1; iFin < nBoutons; ++iFin){
        for (int iLettre = 0; iLettre < nLettres; ++iLettre){
            int valMin = -1;
            if (iFin - lenCombo >= lenCombo - 1)
                valMin = dp[iFin - lenCombo][iLettre][1];

            else
                valMin = 0;
            //valMin = OO;
            dp[iFin][iLettre][0] = valMin + sum[iFin][iLettre];
        /*  valMin = OO;
            for (int i = 0; i <= iFin - lenCombo; ++i)
                for (int j = 0; j < nLettres; ++j)
                    dp[iFin][iLettre][0] = min(dp[iFin][iLettre][0], dp[i][j][0] + sum[iFin][iLettre] - sum[i][iLettre]);
            for (int j = 0; j < nLettres; ++j)
                dp[iFin][iLettre][0] = min(dp[iFin][iLettre][0], sum[iFin][iLettre]);*/
        }

        /*for (int iLettre = 0; iLettre < nLettres; ++iLettre)
            cout << dp[iFin][iLettre] << "\t";
        cout << endl;
        */
        if (iFin != nBoutons - 1){
            int mini = OO;
            for (int iLettre = 0; iLettre < nLettres; ++iLettre)
                mini = min(mini, dp[iFin][iLettre][0]);

            for (int iLettre = 0; iLettre < nLettres; ++iLettre){
                dp[iFin][iLettre][1] = mini - sum[iFin][iLettre];

                if (iFin >= lenCombo)
                    //int enlevement = sum[iFin][iLettre] - sum[iFin - 1][iLettre];
                    dp[iFin][iLettre][1] = min(dp[iFin][iLettre][1], dp[iFin - 1][iLettre][1]);
                dp[iFin][iLettre][1] = min(dp[iFin][iLettre][1], 0);
            }
        }
    }

    /*cout << "-\n";
    for (int j = 0; j < nBoutons; ++j){
    for (int i = 0; i < nLettres; ++i)
        cout << dp[j][i] << " ";
    cout << endl;}*/
    int mini = OO;
    for (int iLettre = 0; iLettre < nLettres; ++iLettre)
        mini = min(mini, dp[nBoutons - 1][iLettre][0]);
    cout << mini << endl;
    return 0;
}