P8013 [COCI 2013/2014 #4] GMO

给定一个由 `A` `C` `G` `T` 组成的字符串，你需要在这个字符串中插入若干个 `A` `C` `G` `T`，使字符串中包含目标字符串，并使花费的代价最少。 其中插入不同的字符花费的代价也是不同的。

第一行，一个字符串 $N$，代表原字符串； 第二行，一个字符串 $M$，代表目标字符串； 第三行，四个正整数 $a,c,g,v$，分别表示插入一个 `A` 花费的代价，插入一个 `C` 花费的代价，插入一个 `G` 花费的代价，插入一个 `T` 花费的代价。

一行，一个正整数，表示最小花费。

**【样例解释 #1】** 可能的方法中有：`GTCAT`，花费 $10$，可以证明是最小花费。 **【数据范围】** 对于 $80\%$ 的数据，$1\le |N|,|M|\le 2000$； 对于 $100\%$ 的数据，$1\le |N|\le 10000$，$1\le |M|\le 5000$，$0\le a,c,g,v\le 1000$。 **【来源】** 本题分值按 COCI 原题设置，满分 $80$。 题目译自 [COCI2013-2014 CONTEST #4](https://hsin.hr/coci/archive/2013_2014/contest4_tasks.pdf) _**T2 GMO**_。