Genetically Modified Apple

Time limit1sMemory limit128 MB

Summary

Insert priced letters into a DNA string so a given gene appears as a contiguous block at minimum total cost.

Level: Medium6 of 10
Topics: Dynamic programming, String matching
Solved: No attempts yet

Problem

A multinational company asks you to help them genetically modify an apple. For the apples to grow faster, to get more of them, to make them bigger and to make them look nicer and more symmetrical, the apple's DNA needs an insertion of a certain swine gene.

The apple's DNA is written as a string over the four characters A, C, G, T. The swine gene is written over the same four characters. Characters may be inserted at any positions of the apple's DNA, so that the finished string contains the swine gene in successive locations. To make things a bit more complicated, inserting one A, one C, one G or one T each has its own cost.

Help this company reach its goal at the lowest possible total cost. As a reward, you get a ton of their apples.

Input

The first line contains a string of $N$ characters that represents the apple's DNA. ( $1 \le N \le 10000$ )

The second line contains a string of $M$ characters that represents the swine gene to insert. ( $1 \le M \le 5000$ )

Both strings consist only of the characters A, C, G, T.

The third line contains four integers, the cost of inserting one A, one C, one G and one T, in that order. Each of the four values is between 0 and 1000.

Output

On the first line, print the smallest possible total insertion cost.

Hint

Look at the first example. Several ways make the swine gene appear in successive locations. GCATA costs 7 + 5, and GTCAT costs 7 + 3. The bold characters are the inserted ones.

Examples3

Example 1
Input
```
GTA
CAT
5 7 1 3
```
Expected output
```
10
```
Example 2
Input
```
TATA
CACA
3 0 3 0
```
Expected output
```
3
```
Example 3
Input
```
TCGCGAG
TGCAG
10 10 15 15
```
Expected output
```
25
```