Moortal Cowmbat

Bessie has been playing the popular fighting game Moortal Cowmbat for a long time. However, the game developers have recently rolled out an update that forces Bessie to change her play style.

The game uses $M$ buttons labeled by the first $M$ lowercase letters ($1 \leq M \leq 26$). Bessie's favorite combo in the game is a length-$N$ string $S$ of button presses ($1 \leq N \leq 10^5$). Because of the most recent update, every combo must now be made from a series of "streaks", where a streak is a series of the same button pressed at least $K$ times in a row ($1 \leq K \leq N$). Bessie wants to modify her favorite combo into a new combo of the same length $N$ that is made from streaks of button presses, so that it satisfies the changed rules.

Bessie needs $a_{ij}$ days to train herself to press button $j$ instead of button $i$ at any specific location in her combo. That is, it costs $a_{ij}$ to change a single specific letter in $S$ from $i$ to $j$. Switching from button $i$ to an intermediate button $k$ and then from button $k$ to button $j$ may take less time than switching from $i$ to $j$ directly. More generally, there may be a path of changes that starts at $i$ and ends at $j$ and gives the best overall cost for switching from button $i$ ultimately to button $j$.

Help Bessie determine the smallest possible number of days she needs to create a combo that satisfies the new requirements.

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

Output a single number, representing the minimum number of days Bessie needs to change her combo into one that satisfies the new requirements.

The optimal solution in this example is to change the a into b, change the d into e, and then change both e's into c's. This takes $1+4+0+0=5$ days, and the final combo string is bbccc.