题目描述

Bessie 玩格斗游戏真牛快打已经有很长时间了。然而，最近游戏开发者发布了一项更新，这迫使 Bessie 改变她的打法。

游戏总共使用 $M$ 个按键，标记为前 $M$ 个小写字母。Bessie 在游戏中最喜欢的组合键是一个长为 $N$ 的按键字符串 $S$。然而，由于最近的更新，现在每种组合键必须由一些“连击”所组成，其中连击的定义为相同的按键连续按下至少 $K$ 次。Bessie想要修改她最喜欢的组合键，创造一个同样长为 $N$ 的新组合键，然而这一新组合键由按键连击所组成，以适应规则的变化。

Bessie 需要消耗 $a_{ij}$ 天来训练她在组合键中某个特定的位置用按键 $j$ 来取代按键 $i$（也就是说，将 $S$ 中的某个特定的字符由 $i$ 变为 $j$ 的代价为 $a_{ij}$）。注意有可能将按键 $i$ 换成某种中间按键 $k$ 然后再从按键 $k$ 换成按键 $j$ 会比直接从按键 $i$ 换成按键 $j$ 消耗更短的时间（或者更一般地说，可能有一条起点为 $i$ 终点为 $j$ 的更改路径给出了从按键 $i$ 最终更改为按键 $j$ 的最小总代价）。

帮助 Bessie 求出她创建一个满足新要求的组合键所需要的最小天数。

输入格式

输入的第一行包含 $N$，$M$ 和 $K$。第二行包含 $S$，最后 $M$ 行包含一个 $M\times M$ 的数字方阵 $a_{ij}$，其中 $a_{ij}$ 为一个范围为 $0 \ldots 1000$ 的整数，并且对于所有的 $i$，有 $a_{ii} = 0$。

输出格式

输出一个整数，表示 Bessie 将她的组合键改为一个满足新要求的新的组合键所需要的最小天数。

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

5

提示

在这个例子中的最优方案是将 a 改为 b，将 d 改为 e，再将两个 e 都改为 c。这总共消耗 $1+4+0+0=5$ 天，最终的组合键为 bbccc。

测试点性质：

测试点 $2\sim 4$ 满足 $N\le 1000$，$K\le 50$。

测试点 $5\sim 8$ 满足 $N\le 3\times 10^4$，$K\le 50$。

对于 $100\%$ 的数据，$1 \leq M \leq 26$，$1 \leq K\leq N \leq 10^5$。

供题：Eric Wei