You are tasked with transcribing a passage. This passage consists of several symmetric characters (no more than 26 types of symmetric characters, represented by $a-z$ for convenience). For each character $ch$ you transcribe, you incur a cost of $cost_{ch}$.

As a student, you have mastered a clever trick: you can fold the paper so that the ink already transcribed is copied onto the other half, thereby avoiding repetitive mechanical work.

Formally, assuming the current transcription progress is $s_1s_2 \dots s_m$, you can perform the following two operations:

• Operation 1: Fold the paper right after $s_m$, making the transcription progress $s_1s_2 \dots s_m s_m s_{m-1} \dots s_k$, where $1 \le k \le m$.
• Operation 2: Fold the paper exactly in the middle of $s_m$, making the transcription progress $s_1s_2 \dots s_m s_{m-1} \dots s_k$, where $1 \le k < m$.

Given that each fold takes time $C$, what is the minimum time required to finish transcribing the passage?

Input

The first line contains two integers $n$ and $C$, representing the length of the string to be transcribed and the time required for each fold.

The second line contains 26 integers, where the $i$-th integer $cost_i$ represents the time required to transcribe the $i$-th character.

The third line contains a string $s$ of length $n$, guaranteed to consist only of lowercase letters.

Output

Output a single integer representing the minimum time required to transcribe the passage.

Examples

Input 1

20 2
9 1 7 5 2 1 10 1 6 7 9 10 5 2 6 4 1 10 10 6 5 8 5 5 5 3
aaabedcecdebccadecbc

Output 1

67

Note

Initial $s=""$

1. Transcribe $a$, cost 9, $s="a"$;
2. Choose Operation 1, cost 2, $s="aa"$;
3. Choose Operation 2, cost 2, $s="aaa"$;
4. Transcribe $b$, cost 1, $s="aaab"$;
5. Transcribe $e$, cost 2, $s="aaabe"$;
6. Transcribe $d$, cost 5, $s="aaabed"$;
7. Transcribe $c$, cost 7, $s="aaabedc"$;
8. Transcribe $e$, cost 2, $s="aaabedce"$;
9. Choose Operation 2, cost 2, $s="aaabedcecdeb"$;
10. Transcribe $c$, cost 7, $s="aaabedcecdebc"$;
11. Choose Operation 1, cost 2, $s="aaabedcecdebcc"$;
12. Transcribe $a$, cost 9, $s="aaabedcecdebcca"$;
13. Transcribe $d$, cost 5, $s="aaabedcecdebccad"$;
14. Transcribe $e$, cost 2, $s="aaabedcecdebccade"$;
15. Transcribe $c$, cost 7, $s="aaabedcecdebccadec"$;
16. Transcribe $b$, cost 1, $s="aaabedcecdebccadecb"$;
17. Choose Operation 2, cost 2, $s="aaabedcecdebccadecbc"$;

Total cost is 67.