Bessie gioca da tempo al popolare gioco di combattimento Moortal Cowmbat. Ma un aggiornamento recente impone di cambiare stile.

Ci sono $M$ pulsanti, le prime $M$ minuscole ($1 \leq M \leq 26$). La combo preferita è stringa $S$ lunga $N$ ($1 \leq N \leq 10^5$). Ora ogni combo deve essere composta da «serie»: lo stesso pulsante premuto almeno $K$ volte consecutive ($1 \leq K \leq N$). Vuole modificarla mantenendo lunghezza $N$ e formando serie valide.

Allenarsi a premere $j$ invece di $i$ in una posizione specifica richiede $a_{ij}$ giorni, costo per cambiare una sola lettera specifica di $S$ da $i$ a $j$. Passare da $i$ al pulsante intermedio $k$, poi a $j$, può essere più veloce del diretto. In generale una catena di cambi da $i$ a $j$ può dare il miglior costo totale.

Trovate il minimo di giorni per creare una combo valida.

Input

La prima riga contiene $N$, $M$, $K$, la seconda $S$, le ultime $M$ una matrice $M\times M$ di interi $a_{ij}$ in $0 \ldots 1000$, con $a_{ii} = 0$ per ogni $i$.

Output

Stampate un numero, i giorni minimi per adattare la combo.

Esempi

Input 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

Output 1

5

Spiegazione

L’ottimo cambia a in b, d in e, poi entrambe le e in c. Richiede $1+4+0+0=5$ giorni e produce bbccc.

Punteggio

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

Autore del problema: Eric Wei