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 求出她创建一个满足新要求的组合键所需要的最小天数。