Bessie는 인기 격투 게임 Moortal Cowmbat을 오래 해 왔다. 하지만 개발자의 최근 업데이트로 플레이 스타일을 바꿔야 한다.

버튼은 첫 $M$개 소문자로 나타내는 $M$개 ($1 \leq M \leq 26$)이다. 좋아하는 콤보는 길이 $N$ 문자열 $S$ ($1 \leq N \leq 10^5$)이다. 이제 콤보는 같은 버튼을 적어도 $K$번 연속 누른 “연속 구간” ($1 \leq K \leq N$)들로 구성해야 한다. 길이 $N$을 유지해 규칙에 맞는 구간들로 바꾸려 한다.

특정 위치에서 $i$ 대신 $j$를 누르게 훈련하려면 $a_{ij}$일이 든다. 즉 $S$의 특정 한 글자를 $i$에서 $j$로 바꾸는 비용이다. $i$에서 중간 버튼 $k$, 다시 $k$에서 $j$로 바꾸면 직접보다 빠를 수 있다. 일반적으로 $i$에서 $j$까지 변경 경로가 최선의 총 비용을 줄 수 있다.

새 요구에 맞는 콤보를 만드는 최소 일수를 구하라.

입력

첫 줄은 $N$, $M$, $K$, 둘째 줄은 $S$, 마지막 $M$줄은 $0 \ldots 1000$ 정수 $a_{ij}$의 $M\times M$ 행렬이며 모든 $i$에 $a_{ii} = 0$이다.

출력

콤보를 조건에 맞게 바꾸는 최소 일수 하나를 출력하라.

예제

입력 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

출력 1

5

참고

최적은 a를 b, d를 e, 그 뒤 두 e를 c로 바꾸는 것이다. $1+4+0+0=5$일이며 최종 bbccc이다.

서브태스크

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

문제 출제자: Eric Wei