Min Cost to Remove Subsequence (Minimal Cost To Strengthen Password :)

Delete some characters of the password; the cost of deleting one copy of each letter a..z is given by the 26 entries of cost. No permutation of the remaining password may contain target as a subsequence. Minimize the cost. This is not only about forbidding target in the original order, and you are not required to delete every copy of a letter.

输入格式

The first line contains pwd, the second line contains target, and the third line contains exactly 26 cost values. In the original statement both strings have length 1..100000 and are lowercase, and cost≥0; the upper bound on cost was written as 10° and marked unconfirmed, so this site adds 0≤cost[i]≤10^9. The 26 entries in the body clearly correct the corrupted index 251.

输出格式

Output a single integer, the answer.

样例 1

输入：

abcdcbcb
bcb
2 3 1 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

输出：

3

样例 2

输入：

kkkk
k
5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5

输出：

20

样例 3

输入：

adefgh
hf
1 0 0 2 4 4 3 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

输出：

1

样例说明

The answers are 3, 20 and 1 respectively. In the first example, deleting three c's at 1 each is cheaper than deleting two b's at 3 each; the extra zeros in the source cost array are corrected to the formal 26 entries. In the second example the original explanation wrongly says 5 k's; there are actually 4, at 5 each, for a total of 20.