Moortal Kombat#10292

Moortal Kombat

1 second

128 megabytes

Hard

Bessie has been playing the popular game Moortal Kombat for a long time. However, the game developers have recently released an update that forces her to change her usual play style.

The game uses $m$ buttons, labeled with the first $m$ lowercase letters of the Latin alphabet. Bessie's favorite combination of moves is a string $s$ of length $n$ , describing a sequence of button presses. After the update, each combo must consist of a sequence of "stripes", where a stripe is defined as a consecutive sequence of the same button pressed at least $k$ times in a row. Bessie wants to modify her favorite combination to obtain a new string of the same length $n$ , but consisting of stripes that satisfy the updated rules.

It is known that Bessie needs $a_{ij}$ a_{ij} days to learn to press button $j$ instead of button $i$ in any specific position of her combination (that is, replacing one occurrence of letter $i$ in $s$ with letter $j$ costs $a_{ij}$ a_{ij} days).

Note that sometimes the replacement can be done faster through intermediate buttons. For example, changing $i$ directly to $j$ may be more expensive than performing two consecutive replacements $i \to k \to j$ i \rightarrow k \rightarrow j. Thus, there may exist a transformation path from $i$ to $j$ with a smaller total cost than the direct replacement.

Help Bessie determine the minimum number of days required to create a combination that satisfies the new requirements.

Input

The first line contains three integers: $n$ $(1 \leq n \leq 1 0^{5})$ (1 \le n \le 10^5), $m$ $(1 \leq m \leq 26)$ (1 \le m \le 26), and $k$ $(1 \leq k \leq n)$ (1 \le k \le n).

The second line contains the string $s$ .

The next $m$ lines each contain $m$ integers — the elements of the matrix $a_{ij}$ a_{ij}, where $a_{ij}$ a_{ij} is the number of days required to replace button $i$ with button $j$ . It is guaranteed that $0 \leq a_{ij} \leq 1000$ 0 \le a_{ij} \le 1000 and $a_{ii} = 0$ a_{ii} = 0 for all $i$ .

Output

Print the minimum number of days Bessie needs to create a combination that meets the new requirements.

Examples

Example

Example 1

Note

In this example, the optimal solution is to replace $a$ with $b$ , then replace $d$ with $e$ , and finally replace both $e$ 's with $c$ . The total cost of these changes is $1 + 4 + 0 + 0 = 5$ 1 + 4 + 0 + 0 = 5 days, and the resulting string will be $bb ccc$ .