Bessie has been playing the popular fighting game Moortal Cowmbat for a long time now. 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 by the first $M$ lowercase letters ($1 \leq M \leq 26$). Bessie's favorite combo of moves in the game is a length-$N$ string $S$ of button presses ($1 \leq N \leq 10^5$). However, 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 ($1 \leq K \leq N$). Bessie wants to modify her favorite combo to produce a new combo of the same length $N$, but made from streaks of button presses to satisfy the change in 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}$ 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 from $i$ to $j$ directly (or more generally, there may be a path of changes starting with $i$ and ending with $j$ that 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 supports the new requirements.

Input

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

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

Examples

Input 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

Output 1

5

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 will take $1+4+0+0=5$ days, and the final combo string will be bbccc.

Scoring

• Test cases 2-4 satisfy $N\le 1000, K\le 50.$
• Test cases 5-8 satisfy $N\le 30,000, K\le 50.$

Problem credits: Eric Wei