Problem Description

Given a string consisting of characters A, C, G, and T, you need to insert some number of A, C, G, and T into this string to make it contain the target string with the minimum cost.

The cost of inserting different characters varies.

Input Format

The first line contains a string $N$, representing the original string.

The second line contains a string $M$, representing the target string.

The third line contains four positive integers $a, c, g, v$, which respectively represent the cost of inserting one A, the cost of inserting one C, the cost of inserting one G, and the cost of inserting one T.

Output Format

A single line containing a positive integer, representing the minimum cost.

Sample Input and Output

Sample Input #1

GTA
CAT
5 7 1 3

Sample Output #1

10

Sample Input #2

TATA
CACA
3 0 3 0

Sample Output #2

3

Sample Input #3

TCGCGAG
TGCAG
10 10 15 15

Sample Output #3

25

Notes

[Sample Explanation #1]

One possible method is GTCAT, which costs $10$, and it can be proven to be the minimum cost.

[Data Range]

For $80\%$ of the data, $1 \le |N|, |M| \le 2000$.

For $100\%$ of the data, $1 \le |N| \le 10000$, $1 \le |M| \le 5000$, $0 \le a, c, g, v \le 1000$.

[Source]

This problem is scored according to the original COCI settings, with a full score of $80$.

The problem is translated from COCI2013-2014 CONTEST #4 T2 GMO.

见题面 Input 部分

见题面 Output 部分