P8013 [COCI 2013/2014 #4] GMO

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.

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 one line with a positive integer, indicating the minimum cost.

**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](https://hsin.hr/coci/archive/2013_2014/contest4_tasks.pdf) _**T2 GMO**_. Translated by ChatGPT 5