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$ を保ち、連続列からなる規則を満たすコンボへ変えたいです。

特定位置で $i$ の代わりに $j$ を押す訓練に $a_{ij}$ 日、つまり $S$ の特定の 1 文字を $i$ から $j$ に変える費用は $a_{ij}$ です。$i$ から中間の $k$、さらに $k$ から $j$ のほうが直接より短いことがあります。一般に $i$ から $j$ への変更経路が最良の総費用を与える場合があります。

新条件を満たすコンボを作る最小日数を求めてください。

入力

1 行目は $N$、$M$、$K$、2 行目は $S$、最後の $M$ 行は $M\times M$ 行列 $a_{ij}$ です。各値は $0 \ldots 1000$ の整数で、全 $i$ に対して $a_{ii} = 0$。

出力

新条件を満たすコンボに変える最小日数を 1 数で出力してください。

入出力例

入力 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