A multinational company is asking you to help them genetically modify an apple. In order for the apples to grow faster, to get more of them, to make them bigger and make them look nicer and more symmetrical, the apple's DNA requires an insertion of a certain swine gene.

The apple's DNA is represented by a series of characters from the set {A, C, G, T}. The required swine gene is also comprised of characters from this set. The apple's DNA should be injected with some characters into some places, so that the resulting sequence contains a swine gene somewhere (in successive locations). To make things a bit more complicated, inserting each of the characters A, C, G, T has its own cost.

Help this multinational company in achieving their goal with the lowest possible total cost. As a reward, you get a ton of their apples.

Input Specification

The first line of input contains a sequence of ~N~ ~(1 \leq N \leq 10\,000)~ characters which represent the apple's DNA.

The second line of input contains a sequence of ~M~ ~(1 \leq M \leq 5\,000)~ characters which represent the swine gene that we want to insert into the apple's DNA.

Both the sequences are comprised only of characters from the set {A, C, G, T}.

The third line of input contains four integers from the interval ~[0, 1000]~: the cost of inserting one character A, C, G, T, in that order.

Output Specification

The first and only line of output must contain the minimal total cost.

Scoring

In test cases worth ~80\%~ of total points, ~N~ and ~M~ will not exceed ~2\,000~.

Sample Input 1

GTA
CAT
5 7 1 3

Sample Output 1

10

Explanation for Sample Output 1

Some of the possible solutions are GCATA and GTCAT (the inserted characters are bolded), the first solution costs ~7 + 5~, the second ~7 + 3~.

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