E. Printer
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Xiao Ming is learning to type using a keyboard. Today, he needs to input a string $$$s$$$ of length $$$n$$$ consisting of lowercase letters only.

Initially:

Xiao Ming's left index finger is on the lowercase letter 'a' on the keyboard.

His right hand is used to press the left/right arrow keys to control the cursor position.

Xiao Ming starts with an empty string $$$s$$$, and the cursor is at the very beginning of the string. Each second, he can perform one of the following three operations:

1. Move his left index finger from the current letter $$$x$$$ to letter $$$y$$$, with a cost of $$$\text{cost}_{x,y}$$$.

2. Press the left or right arrow key to move the cursor left/right by one position, with a cost of $$$t$$$. If the cursor is already at the far left/right, nothing happens.

3. Press the letter currently under his left index finger to print the character to the right of the cursor in the string, with a cost of $$$t$$$.

For example, to print the string $$$\text{aabaa}$$$, Xiao Ming can proceed as follows: 1. Press 'a' four times with his left hand (cost: $$$4t$$$). Now $$$\text{s=aaaa}$$$, cursor after the fourth 'a'. 2. Press the left arrow key twice with his right hand (cost: $$$2t$$$). Now $$$\text{s=aaaa}$$$, cursor after the second 'a'. 3. Move his left hand from 'a' to 'b' (cost: $$$\text{cost}_{a,b}$$$), then press 'b' (cost: $$$t$$$). Now $$$\text{s=aabaa}$$$, cursor after 'b'.

Please help Xiao Ming calculate the minimum total cost required to print the target string $$$s$$$.

Input

First line: $$$n$$$, $$$m$$$, $$$t$$$ — the length of string $$$s$$$, the size of the character set $$$m$$$, and the cost $$$t$$$ for moving the cursor or printing a single character.

Second line: The string $$$s$$$ (guaranteed $$$|s|=n$$$, $$$\text{'a'} \leq s_i \leq \text{'a'}+m-1$$$).

Next $$$m$$$ lines: Each line contains $$$m$$$ integers. The $$$j$$$-th integer in the $$$i$$$-th line, $$$\text{cost}_{i,j}$$$, represents the cost to move from character $$$\text{'a'}+i-1$$$ to $$$\text{'a'}+j-1$$$.

$$$1 \leq n \leq 20$$$,

$$$1 \leq m \leq 26$$$,

$$$0 \leq t, \text{cost}_{i,j} \leq 10^5$$$,

$$$\text{cost}_{i,i} = 0$$$ for all $$$i$$$,

For any $$$i,j,k$$$, $$$\text{cost}_{i,j} \leq \text{cost}_{i,k} + \text{cost}_{k,j}$$$ (triangle inequality).

Output

A single integer representing the answer.

Examples
Input
5 2 1
aabaa
0 10
10 0
Output
17
Input
5 2 1
abaaa
0 1
1 0
Output
7