Bessie 玩流行格斗游戏 Moortal Cowmbat 已很久，但开发者最近的更新迫使她改变玩法。

游戏有 $M$ 个按钮，以前 $M$ 个小写字母标记（$1 \leq M \leq 26$）。她最喜欢的连招是长度为 $N$ 的按键字符串 $S$（$1 \leq N \leq 10^5$）。更新后每个连招必须由若干“连续段”组成，即同一按钮连续按至少 $K$ 次（$1 \leq K \leq N$）。她想修改最爱的连招，得到同长 $N$ 且符合规则的连续段连招。

她训练在连招的一个指定位置按按钮 $j$ 而非 $i$ 需要 $a_{ij}$ 天，即把 $S$ 的某一个字母从 $i$ 改为 $j$ 的费用为 $a_{ij}$。先从 $i$ 改为中间按钮 $k$ 再从 $k$ 改为 $j$ 可能比直接改更快；更一般地，从 $i$ 到 $j$ 的某条修改路径可能给出最终转换的最优总费用。

帮助 Bessie 求出构造满足新要求的连招最少需要的天数。

输入格式

第一行含 $N$、$M$、$K$；第二行含 $S$；最后 $M$ 行为 $M\times M$ 矩阵 $a_{ij}$，每个值为 $0 \ldots 1000$ 的整数，所有 $i$ 满足 $a_{ii} = 0$。

输出格式

输出一个数，表示她把连招改为符合新要求的连招所需最少天数。

样例

输入格式 1

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

输出格式 1

5

说明

此例最优是 a 改 b、d 改 e，然后两个 e 都改 c。共需 $1+4+0+0=5$ 天，最终字符串 bbccc。

子任务

• 测试点 2–4 满足 $N\le 1000, K\le 50.$
• 测试点 5–8 满足 $N\le 30,000, K\le 50.$

题目作者：Eric Wei