Problem 3. Moortal Cowmbat

USACO 2019 December Contest, Gold

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

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

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

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

测试点性质： 测试点 2-4 满足 $N\le 1000, K\le 50$。测试点 5-8 满足 $N\le 30,000, K\le 50$。

输入格式（文件名：cowmbat.in）：

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

输出格式（文件名：cowmbat.out）：

输出一个整数，表示 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。

供题：Eric Wei