Bessie joga há muito tempo o popular jogo de luta Moortal Cowmbat. Mas uma atualização recente exige mudar seu estilo.

Há $M$ botões, as primeiras $M$ letras minúsculas ($1 \leq M \leq 26$). Seu combo preferido é string $S$ de comprimento $N$ ($1 \leq N \leq 10^5$). Agora cada combo deve ser feito de «sequências»: apertar o mesmo botão pelo menos $K$ vezes seguidas ($1 \leq K \leq N$). Quer alterá-lo mantendo comprimento $N$ e formando sequências válidas.

Treinar para apertar $j$ em vez de $i$ numa posição específica leva $a_{ij}$ dias, custo de mudar uma letra específica de $S$ de $i$ para $j$. Passar de $i$ por um botão intermediário $k$ e depois para $j$ pode ser mais rápido que diretamente. Em geral uma cadeia de mudanças de $i$ a $j$ pode dar o melhor custo total.

Ache o mínimo de dias para criar um combo válido.

Entrada

A primeira linha contém $N$, $M$, $K$, a segunda $S$, as últimas $M$ uma matriz $M\times M$ de inteiros $a_{ij}$ em $0 \ldots 1000$, com $a_{ii} = 0$ para todo $i$.

Saída

Imprima um número, mínimo de dias para adaptar o combo.

Exemplos

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

Saída 1

5

Explicação

O ótimo muda a para b, d para e, depois ambas e para c. Leva $1+4+0+0=5$ dias e termina em bbccc.

Pontuação

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

Créditos do problema: Eric Wei