Bessie’s Combo Transformation

Bessie has been playing the fighting game "Ultimate Beat" for a long time. Recently, the game developers released an update that forced Bessie to change her play style. In the game, there are M keys labeled as the first M lowercase letters. Bessie’s favorite combo is given by a string S of length N.

Due to the update, every combo must now be composed of one or more "combos" (or streaks). A streak is defined as a consecutive sequence of the same key pressed at least K times. Bessie wants to modify her favorite combo to a new combo (also of length N) so that it can be partitioned into valid streaks according to the new rule.

For training purposes, Bessie must spend a_ij days to change a specific position in the combo from key i to key j. Note that it might be cheaper to change key i into some intermediate key k before finally changing it into key j (in other words, there might be a transformation path with lower total cost than a direct change from i to j).

Your task is to help Bessie compute the minimum number of days required to create a valid combo that meets the new requirements.

Note: Any formulas included are in LaTeX format. For instance, the cost matrix is represented as $a_{ij}$ and the favorite combo has length $N$. The update rule requires each streak to have length at least $K$.

inputFormat

The input begins with a line containing three integers N, M, and K where:

• N is the length of the combo string,
• M is the number of keys (the first M lowercase letters), and
• K is the minimum number of consecutive key presses required for a streak.

The next line contains the combo string S of length N (each character is among the first M lowercase letters).

This is followed by M lines, each containing M integers. The integer on the i-th row and j-th column represents $a_{ij}$, the number of days required to change key i (represented by the i-th lowercase letter) to key j.

outputFormat

Output a single integer representing the minimum number of days required for Bessie to transform her original combo into a valid combo according to the updated rules.

sample

5 3 2
a bcba
0 1 2
1 0 1
2 1 0

3