Moortal Cowmbat.
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 botones etiquetados con las primeras letras minúsculas . El combo de movimientos favorito de Bessie en el juego es una cadena de longitud de pulsaciones de botones . 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 veces seguidas . Bessie quiere modificar su combo favorito para producir un nuevo combo de la misma longitud pero hecho con rachas de pulsaciones de botones para satisfacer el cambio de reglas. Bessie tarda días para entrenarse a sí misma en pulsar el botón en lugar del botón en cualquier lugar específico de su combo (es decir, cuesta cambiar una sola letra específica en de a ). Obsérvese que puede llevar menos tiempo pasar de usar el botón a un botón intermedio y luego del botón al botón en lugar de pasar de a directamente (o, de forma más general, puede haber una ruta de cambios que empiece con y termine con que ofrezca el mejor coste global para pasar del botón en última instancia al botón ).
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
Los casos de prueba del 2 al 4 satisfacen .
Los casos de prueba del 5 al 8 satisfacen .
Entrada
La primera línea de entrada contiene y . La segunda línea contiene , y las últimas líneas contienen una matriz de valores , donde es un entero en el rango y para todo .
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 por la , cambiar la por la , y luego cambiar las dos por la . Esto tomará días, y la cadena combinada final será .
Comments