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 is forcing Bessie to change her play style.

The game uses $m$ buttons, labeled with the first $m$ lowercase letters. Bessie's favorite combo of moves in the game is a string $s$ of length $n$, consisting of button presses. Due to the most recent update, every combo must now be made from a series of "streaks," where a streak is defined as a series of the same button pressed at least $k$ times in a row. Bessie wants to modify her favorite combo to produce a new combo of the same length $n$, but composed of streaks of button presses to satisfy with the new rules.

It takes $a_{ij}$ days for Bessie to train herself to press button $j$ instead of button $i$ at any specific location in her combo (i.e., it costs $a_{ij}$ days to change a single specific letter in $s$ from $i$ to $j$). Note that it might take less time to switch from using button $i$ to an intermediate button $k$ and then from button $k$ to button $j$ rather than directly from $i$ to $j$ (more generally, there may be a path of changes starting with $i$ and ending with $j$ that provides 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 meets the new requirements.

Input

The first line contains three integers: $n(1\le n\le 10^5)$, $m(1\le m\le 26)$ and $k(1\le k\le n)$. The second line contains the string $s$. The next $m$ lines contain an $m\times m$ matrix of values $a_{ij}$, where $a_{ij}$ is an integer in the range $\mathrm{0..1000}$ and $a_{ii}=0$ for all $i$.

Output

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

Examples

In the optimal solution for this example, change the $a$ into $b$, the $d$ into $e$, and both $e$'s into $c$'s. This will take $1+4+0+0=5$ days, and the final combo string will be $bbccc$.