Bessie spielt schon lange das beliebte Kampfspiel Moortal Cowmbat. Doch ein kürzliches Update zwingt sie, ihren Spielstil zu ändern.

Das Spiel hat $M$ Tasten, die ersten $M$ Kleinbuchstaben ($1 \leq M \leq 26$). Ihre Lieblingskombo ist eine Zeichenkette $S$ der Länge $N$ ($1 \leq N \leq 10^5$). Jetzt muss jede Kombo aus „Serien“ bestehen: mindestens $K$ gleiche Tastendrücke hintereinander ($1 \leq K \leq N$). Sie will ihre Kombo bei gleicher Länge $N$ in solche regelgerechten Serien umwandeln.

Das Training, an einer bestimmten Position $j$ statt $i$ zu drücken, braucht $a_{ij}$ Tage, also die Kosten einer einzelnen bestimmten Buchstabenänderung in $S$ von $i$ nach $j$. Über eine Zwischentaste $k$, erst $i$ nach $k$, dann $k$ nach $j$, kann es schneller als direkt gehen. Allgemein kann eine Änderungskette von $i$ nach $j$ die besten Gesamtkosten liefern.

Bestimme die minimale Zahl Tage für eine regelgerechte Kombo.

Eingabe

Die erste Zeile enthält $N$, $M$, $K$, die zweite $S$, die letzten $M$ eine $M\times M$-Matrix ganzer Werte $a_{ij}$ in $0 \ldots 1000$, mit $a_{ii} = 0$ für alle $i$.

Ausgabe

Gib eine Zahl aus, die minimale Tageszahl für die Änderung in eine regelgerechte Kombo.

Beispiele

Eingabe 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

Ausgabe 1

5

Hinweis

Optimal ist a nach b, d nach e, dann beide e nach c. Das kostet $1+4+0+0=5$ Tage und ergibt bbccc.

Teilaufgaben

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

Aufgabenautor: Eric Wei