Moortal Cowmbat.


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 128M

Author:
Problem types
Allowed languages
C, C#, C++, Java, Pascal, Python, VB

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.


Comments

There are no comments at the moment.