时间限制：1秒　　内存限制：256M

---

【题目描述】

　　很奇怪，小H最近经常做关于改造单词的梦，这可能与最近沉迷于背单词有关。

　　这天晚上，小H又早早地上床睡觉，果不其然，梦如期而至。在梦里，英语老师让他改造一个包含 \(N\) 个字母的复杂单词，要求改的尽量简单且代价最小。具体说来就是把单词改造成若干段，每一段至少是 \(K\) 个相同的字母。并提供给小H一张花费表，其中 $a_{ij}表示把字母i改造成j的花费。

　　小H在梦里无法完成，但梦醒后依然清楚地记得这个问题，于是他决定用编程方法来解决。请你帮助他圆了这个梦。

【输入格式】

　　输入的第一行包含 \(N、M\)和\(K\)。第二行是单词 \(S\)，仅包含前M个小写字母。最后 \(M\) 行包含一个 \(M×M\) 的费用表，表格中 \(a_{ij}\) 为一个范围为 0..1000 的整数，表示把第 \(i\) 个小写字母改成第 \(j\) 个小写字母的花费。并且对于所有的 \(i\) 有 \(a_{ii}=0\)。

【输出格式】

　　输出一个整数，表示最小代价。

【输入输出样例1】

　Input

5 5 2
abcde
0 1 4 4 4
2 0 4 4 4
6 5 0 3 2
5 5 5 0 4
3 7 0 5 0

　Output

5

【样例1解释】

　　在这个例子中的最优方案是将 a 改为b，将d改为e，再将两个e 都改为c，即把单词改成了bbccc。总花费为：1+4+0+0=5。

【输入输出样例2】

　Input

18 6 3
cdfbaeaccdfeafbefd
0 50 20 30 40 10
20 0 13 21 17 35
32 19 0 21 34 37
13 36 40 0 33 48
39 21 16 10 0 34
19 10 23 28 24 0

　Output

216

【测试点性质】

　　共20个测试点，其中：
　　测试点 1—4 满足 \(N≤1000，K≤50\)。
　　测试点 5—8 满足 \(N≤3×104，K≤50\)。
　　所有测试点满足 \(1≤M≤26，1≤K≤N≤10^5\)。

【来源】

　　Mr.he