Problem Description

Bessie has been playing the fighting game "Moortal Cowmbat" for a long time. However, the game developers recently released an update that forces Bessie to change her playstyle.

The game uses a total of $M$ keys, labeled as the first $M$ lowercase letters. Bessie's favorite combo in the game is a key string $S$ of length $N$. However, due to the recent update, every combo must be made up of some "combos", where a combo is defined as pressing the same key consecutively at least $K$ times. Bessie wants to modify her favorite combo to create a new combo of the same length $N$, but this new combo must be composed of such key combos to fit the new rules.

Bessie needs to spend $a_{ij}$ days to train herself to replace key $i$ with key $j$ at a specific position in the combo (that is, the cost to change a specific character in $S$ from $i$ to $j$ is $a_{ij}$). Note that it may be faster to change key $i$ to some intermediate key $k$ and then change key $k$ to key $j$ than to change directly from key $i$ to key $j$ (or, more generally, there may be a change path from $i$ to $j$ that gives the minimum total cost to finally change $i$ into $j$).

Help Bessie find the minimum number of days needed to create a combo that satisfies the new requirements.

Input Format

The first line contains $N$, $M$, and $K$. The second line contains $S$. The last $M$ lines contain an $M\times M$ matrix of integers $a_{ij}$, where $a_{ij}$ is an integer in the range $0 \ldots 1000$, and for all $i$, $a_{ii} = 0$.

Output Format

Output one integer, the minimum number of days needed for Bessie to change her combo into a new combo that satisfies the new requirements.

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

Hint

In this example, the optimal plan is to change a to b, change d to e, and then change both e characters to c. This costs a total of $1+4+0+0=5$ days, and the final combo is bbccc.

Test point properties:

Test points $2\sim 4$ satisfy $N\le 1000$, $K\le 50$.

Test points $5\sim 8$ satisfy $N\le 3\times 10^4$, $K\le 50$.

For $100\%$ of the data, $1 \leq M \leq 26$, $1 \leq K\leq N \leq 10^5$.

Problem by: Eric Wei.

Translated by ChatGPT 5