Bessie lleva mucho jugando al popular juego de lucha Moortal Cowmbat. Pero una reciente actualización la obliga a cambiar su estilo.

Hay $M$ botones, las primeras $M$ minúsculas ($1 \leq M \leq 26$). Su combo favorito es una cadena $S$ de longitud $N$ ($1 \leq N \leq 10^5$). Ahora todo combo debe constar de «rachas»: pulsar el mismo botón al menos $K$ veces seguidas ($1 \leq K \leq N$). Quiere modificarlo manteniendo longitud $N$ y formando rachas válidas.

Aprender a pulsar $j$ en vez de $i$ en una posición concreta cuesta $a_{ij}$ días, cambiar una sola letra específica de $S$ de $i$ a $j$. Pasar de $i$ a un botón intermedio $k$ y luego a $j$ puede ser más rápido que directamente. En general una cadena de cambios de $i$ a $j$ puede tener el mejor coste total.

Halla los mínimos días para crear un combo válido.

Entrada

La primera línea contiene $N$, $M$, $K$, la segunda $S$, las últimas $M$ una matriz $M\times M$ de enteros $a_{ij}$ en $0 \ldots 1000$, con $a_{ii} = 0$ para todo $i$.

Salida

Imprime un número, los mínimos días para adaptar el combo.

Ejemplos

Entrada 1

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

Salida 1

5

Nota

Lo óptimo cambia a por b, d por e, luego ambas e por c. Tarda $1+4+0+0=5$ días y acaba en bbccc.

Subtareas

• Casos 2–4: $N\le 1000, K\le 50.$
• Casos 5–8: $N\le 30,000, K\le 50.$

Autor del problema: Eric Wei