Bessie has been playing the popular fighting game Moortal Cowmbat for a long time now. However, the game developers have recently rolled out an update that is forcing Bessie to change her play style.The game uses MM buttons labeled by the first MM lowercase letters (1≤M≤261≤M≤26). Bessie's favorite combo of moves in the game is a length-NN string SS of button presses (1≤N≤1051≤N≤105). However, due to the most recent update, every combo must now be made from a series of "streaks", where a streak is defined as a series of the same button pressed at least KK times in a row (1≤K≤N1≤K≤N). Bessie wants to modify her favorite combo to produce a new combo of the same length NN, but made from streaks of button presses to satisfy the change in rules.

It takes aijaij days for Bessie to train herself to press button jj instead of button ii at any specific location in her combo (i.e. it costs aijaij to change a single specific letter in SS from ii to jj). Note that it might take less time to switch from using button ii to an intermediate button kk and then from button kk to button jj rather than from ii to jj directly (or more generally, there may be a path of changes starting with ii and ending with jj that gives the best overall cost for switching from button ii ultimately to button jj).

Help Bessie determine the smallest possible number of days she needs to create a combo that supports the new requirements.

SCORING:

• Test cases 2-4 satisfy N≤1000,K≤**50.**N≤1000,K≤50.
• Test cases 5-8 satisfy N≤30,000,K≤**50.**N≤30,000,K≤50.

INPUT FORMAT (file cowmbat.in):

The first line of input contains NN, MM, and KK. The second line contains SS, and the final MM lines contain an M×MM×M matrix of values aijaij, where aijaij is an integer in the range 0…10000…1000 and aii=0aii=0 for all ii.

OUTPUT FORMAT (file cowmbat.out):

Output a single number, representing the minimum number of days Bessie needs to change her combo into one that satisfies the new requirements.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

5

The optimal solution in this example is to change the a into b, change the d into e, and then change both e’s into c’s. This will take 1+4+0+0=51+4+0+0=5 days, and the final combo string will be bbccc.