격투 게임

지원은 격투 게임 'Mortal Cowmbat'을 오랫동안 즐겨 했습니다. 하지만, 최근 게임 개발자들이 업데이트를 통해 지원의 플레이 스타일을 바꾸게 만드는 변경사항을 도입했습니다.

게임에서는 첫 번째 소문자부터 $M$번째 소문자($1 \leq M \leq 26$)로 태깅된 $M$개의 버튼을 사용합니다. 지원이 게임에서 가장 좋아하는 조합은 버튼을 누르는 길이 $N$의 문자열 $S$입니다 ($1 \leq N \leq 10^5$). 

그러나, 가장 최근의 업데이트에 따르면, 이제 모든 조합은 적어도 한번에 $K$번 눌러야 하는 동일한 버튼의 일련의 "연속된" 조합으로 이루어져야 합니다 ($1 \leq K \leq N$). 지원은 자신이 가장 좋아하는 조합을 수정하여 동일한 길이 $N$의 새로운 조합을 만들려고 합니다. 하지만 이 새로운 조합은 버튼을 연속적으로 누르는 규칙을 만족해야 합니다.

지원의 조합에서 특정 위치의 버튼 $i$를 $j$로 바꾸려면 $a_{ij}$ 일이 걸립니다 (즉, $S$에서 특정 문자를 $i$에서 $j$로 바꾸는 데 $a_{ij}$의 비용이 듭니다). $i$에서 $j$로 직접 바꾸는 것보다 $i$에서 중간 버튼 $k$를 사용하고, 다음과 $k$에서 $j$로 바꾸는 것이 더 적은 시간을 소요할 수 있습니다 (또는 더 일반적으로, $i$에서 시작하여 $j$에서 끝나는 최적의 비용을 제공하는 변경 경로가 있을 수 있습니다).

지원이 새로운 요건을 충족하는 조합을 만들기 위해 필요한 최소한의 일 수를 결정하는 데 도움을 주세요.

입력의 첫 번째 줄에는 $N$, $M$, 그리고 $K$가 있습니다. 두 번째 줄에는 $S$가 포함되어 있고, 마지막 $M$ 줄은 $a_{ij}$ 값의 $M \times M$ 행렬을 포함하고 있습니다. 여기서 $a_{ij}$는 $0 \ldots 1000$ 범위 내의 정수이며, 모든 $i$에 대하여 $a_{ii} = 0$ 입니다.

지원이 새로운 요구사항을 만족하는 조합으로 자신의 조합을 바꾸는 데 필요한 최소 일수를 나타내는 하나의 숫자를 출력하세요.