Bessie od dawna gra w popularną bijatykę Moortal Cowmbat. Jednak ostatnia aktualizacja zmusza ją do zmiany stylu.

Gra używa $M$ przycisków, pierwszych $M$ małych liter ($1 \leq M \leq 26$). Ulubione combo to napis $S$ długości $N$ ($1 \leq N \leq 10^5$). Teraz każde musi składać się z „serii”: ten sam przycisk co najmniej $K$ razy kolejno ($1 \leq K \leq N$). Chce zmienić ulubione combo, zachowując długość $N$ i tworząc poprawne serie.

Nauczenie się naciskać $j$ zamiast $i$ w konkretnej pozycji wymaga $a_{ij}$ dni: koszt jednej konkretnej zmiany litery $S$ z $i$ na $j$. Przez pośredni przycisk $k$, najpierw $i$ do $k$, potem $k$ do $j$, może być szybciej niż bezpośrednio. Ogólnie łańcuch zmian z $i$ do $j$ może dać najlepszy łączny koszt.

Znajdź minimum dni na poprawne combo.

Wejście

Pierwszy wiersz zawiera $N$, $M$, $K$, drugi $S$, ostatnie $M$ macierz $M\times M$ całkowitych $a_{ij}$ w $0 \ldots 1000$, z $a_{ii} = 0$ dla wszystkich $i$.

Wyjście

Wypisz jedną liczbę, minimalne dni potrzebne do zmiany combo na poprawne.

Przykład

Wejście 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

Wyjście 1

5

Uwagi

Optymalnie a na b, d na e, potem obie e na c. To $1+4+0+0=5$ dni, końcowe bbccc.

Podzadania

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

Autor zadania: Eric Wei