Problem Description

Given a string consisting of A C G T, you need to insert some A C G T into this string so that the resulting string contains the target string, and the total cost is minimized.

The costs of inserting different characters are also different.

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 represent the cost of inserting an A, the cost of inserting a C, the cost of inserting a G, and the cost of inserting a T, respectively.

Output Format

Output one line with a positive integer, indicating the minimum cost.

GTA
CAT
5 7 1 3 

10

TATA
CACA
3 0 3 0

3

TCGCGAG
TGCAG
10 10 15 15 

25

Hint

Sample Explanation #1.

Among the possible methods is: GTCAT, with cost $10$, and it can be proven to be the minimum cost.

Constraints.

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

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

Source.

The score of this problem follows the original COCI problem settings, with a full score of $80$.

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

Translated by ChatGPT 5