Bessie lleva mucho tiempo jugando al popular juego de lucha Moortal Cowmbat. Sin embargo, los desarrolladores del juego han lanzado recientemente una actualización que obliga a Bessie a cambiar su estilo de juego.

El juego utiliza ~M~ botones etiquetados con las primeras ~M~ letras minúsculas ~(1 \leq M \leq 26)~. El combo de movimientos favorito de Bessie en el juego es una cadena ~S~ de longitud ~N~ de pulsaciones de botones ~(1 \leq N \leq 10^5)~. Sin embargo, debido a la actualización más reciente, ahora cada combo debe hacerse a partir de una serie de "rachas", donde una racha se define como una serie de pulsaciones del mismo botón al menos ~K~ veces seguidas ~(1 \leq K \leq N)~. Bessie quiere modificar su combo favorito para producir un nuevo combo de la misma longitud ~N~ pero hecho con rachas de pulsaciones de botones para satisfacer el cambio de reglas. Bessie tarda ~a_{ij}~ días para entrenarse a sí misma en pulsar el botón ~j~ en lugar del botón ~i~ en cualquier lugar específico de su combo (es decir, cuesta ~a_{ij}~ cambiar una sola letra específica en ~S~ de ~i~ a ~j~). Obsérvese que puede llevar menos tiempo pasar de usar el botón ~i~ a un botón intermedio ~k~ y luego del botón ~k~ al botón ~j~ en lugar de pasar de ~i~ a ~j~ directamente (o, de forma más general, puede haber una ruta de cambios que empiece con ~i~ y termine con ~j~ que ofrezca el mejor coste global para pasar del botón ~i~ en última instancia al botón ~j~).

Ayude a Bessie a determinar el menor número posible de días que necesita para crear una combinación que cumpla los nuevos requisitos.

Restricciones

~\bull~ Los casos de prueba del 2 al 4 satisfacen ~N \leq 1000, K \leq 50~.

~\bull~ Los casos de prueba del 5 al 8 satisfacen ~N \leq 30 000, K \leq 50~.

Entrada

La primera línea de entrada contiene ~N, M~ y ~K~. La segunda línea contiene ~S~, y las últimas ~M~ líneas contienen una matriz ~M \times M~ de valores ~a_{ij}~, donde ~a_{ij}~ es un entero en el rango ~0...1000~ y ~a_{ii} = 0~ para todo ~i~.

Salida

Imprima un solo número, que representa el número mínimo de días que Bessie necesita para cambiar su combo por uno que satisfaga los nuevos requisitos.

Ejemplo de Entrada

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

Ejemplo de Salida

5

La solución óptima en este ejemplo es cambiar la ~a~ por la ~b~, cambiar la ~d~ por la ~e~, y luego cambiar las dos ~e~ por la ~c~. Esto tomará ~1 + 4 + 0 + 0 = 5~ días, y la cadena combinada final será ~bbccc~.