Bessie joue depuis longtemps au jeu de combat populaire Moortal Cowmbat. Mais une mise à jour récente l’oblige à changer de style.

Il y a $M$ boutons, les $M$ premières minuscules ($1 \leq M \leq 26$). Son combo préféré est une chaîne $S$ de longueur $N$ ($1 \leq N \leq 10^5$). Désormais chaque combo doit être fait de « séries », un même bouton pressé au moins $K$ fois de suite ($1 \leq K \leq N$). Elle veut modifier son combo en gardant la longueur $N$, pour le former de telles séries et respecter les règles.

Apprendre à presser $j$ plutôt que $i$ à une position donnée prend $a_{ij}$ jours : c’est le coût pour changer une lettre précise de $S$ de $i$ en $j$. Passer par un bouton $k$, de $i$ à $k$ puis de $k$ à $j$, peut être plus rapide que directement. Plus généralement, une chaîne de changements de $i$ à $j$ peut donner le meilleur coût total.

Trouvez le minimum de jours pour créer un combo conforme.

Entrée

La première ligne contient $N$, $M$, $K$, la deuxième $S$, les dernières $M$ une matrice $M\times M$ de valeurs $a_{ij}$ entières dans $0 \ldots 1000$, avec $a_{ii} = 0$ pour tout $i$.

Sortie

Affichez un nombre, le minimum de jours pour rendre le combo conforme.

Exemples

Entrée 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

Sortie 1

5

Remarque

Ici l’optimum change a en b, d en e, puis les deux e en c. Cela prend $1+4+0+0=5$ jours et donne bbccc.

Sous-tâches

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

Auteur du problème : Eric Wei