d.cpp

#include <bits/stdc++.h>

using namespace std;

#define _ ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'

typedef long long ll;
typedef pair<int, int> ii;

const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;

int main(){ _
	int n, m, k;
	cin >> n >> m >> k;
	string s; cin >> s;
	for (char &c : s) c -= 'a';
	vector<vector<int>> a(m, vector<int>(m));
	for (auto &it : a) for (auto &jt : it) cin >> jt;
	for (int l = 0; l < m; l++)
		for (int i = 0; i < m; i++)
			for (int j = 0; j < m; j++)
				a[i][j] = min(a[i][j], a[i][l] + a[l][j]);
	
		
	
	vector<vector<ll>> w(m, vector<ll>(n+1, 0));
	for (char c = 0; c < m; c++){
		for (int i = n-1; i >= 0; i--)
			w[c][i] = w[c][i+1] + a[s[i]][c];
	}


	auto query = [&](int l, char c){
		int r = l+k-1;
		if (r >= n) return LINF;

		ll cost = w[c][l];
		cost -= w[c][r+1];
		return cost;
	};
	vector<vector<ll>> f(n+1, vector<ll>(m, 0));
	vector<ll> g(n+1, LINF);	
	for (int i = n-k; i >= max(0, n-k-k+1); i--){
		for (int c = 0; c < m; c++){
			if (i == n-k) f[i][c] = query(i, c);
			else f[i][c] = f[i+1][c] + a[s[i]][c];
			g[i] = min(g[i], f[i][c]);
		}
	}


	for (int i = n-k-k; i >= 0; i--){
		for (int c = 0; c < m; c++){
			f[i][c] = f[i+1][c] + a[s[i]][c];
			int j = i+k;
			if (j+k-1 >= n) continue;
			f[i][c] = min(f[i][c], query(i, c) + g[j]);
			g[i] = min(g[i], f[i][c]);
		}
	}
	ll ans = LINF;
	for (char c = 0; c < m; c++)
		ans = min(ans, f[0][c]);
	cout << ans << endl;

		
		
	
	exit(0);
}