무르탈 카우배트

Bessie는 인기 격투 게임 무르탈 카우배트를 오래 즐겨 왔다. 그런데 최근 게임 개발진이 업데이트를 내놓으면서 Bessie는 플레이 방식을 바꿔야 한다.

이 게임은 알파벳 소문자 처음 $M$개로 이름 붙인 $M$개의 버튼을 쓴다($1 \leq M \leq 26$). Bessie가 가장 좋아하는 콤보는 버튼 입력 $N$개로 이루어진 길이 $N$의 문자열 $S$이다($1 \leq N \leq 10^5$). 하지만 최근 업데이트 때문에 모든 콤보는 이제 "연속 구간"의 나열로 만들어야 한다. 연속 구간이란 같은 버튼을 $K$번 이상 연속으로 누른 구간을 말한다($1 \leq K \leq N$). Bessie는 자신이 좋아하는 콤보를 같은 길이 $N$의 새 콤보로 바꾸되, 바뀐 규칙에 맞게 버튼 입력의 연속 구간들로 이루어지도록 만들고 싶다.

Bessie가 콤보의 특정 위치에서 버튼 $i$ 대신 버튼 $j$를 누르도록 연습하는 데는 $a_{ij}$일이 걸린다. 즉 $S$의 특정 글자 하나를 $i$에서 $j$로 바꾸는 데 $a_{ij}$가 든다. 버튼 $i$에서 중간 버튼 $k$로 바꾼 뒤 버튼 $k$에서 버튼 $j$로 바꾸는 편이 $i$에서 $j$로 곧바로 바꾸는 것보다 시간이 덜 걸릴 수도 있다. 더 일반적으로, $i$에서 출발해 $j$로 끝나는 일련의 변경 경로가 $i$를 최종적으로 $j$로 바꾸는 최선의 비용을 줄 수도 있다.

Bessie가 새 규칙을 만족하는 콤보를 만드는 데 필요한 최소 일수를 구하라.

첫째 줄에 $N$, $M$, $K$가 주어진다. 둘째 줄에 $S$가 주어지고, 마지막 $M$개 줄에 $M\times M$ 크기의 값 $a_{ij}$ 행렬이 주어진다. $a_{ij}$는 $0 \ldots 1000$ 범위의 정수이고 모든 $i$에 대해 $a_{ii} = 0$이다.

Bessie가 콤보를 새 규칙을 만족하는 콤보로 바꾸는 데 필요한 최소 일수를 하나의 수로 출력한다.

이 예제의 최적해는 a를 b로 바꾸고, d를 e로 바꾼 뒤, 두 e를 모두 c로 바꾸는 것이다. $1+4+0+0=5$일이 걸리고, 최종 콤보 문자열은 bbccc가 된다.