时间限制：1秒　　内存限制：256M

---

题目描述

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

其中插入不同的字符花费的代价也是不同的。

输入格式

第一行，一个字符串 \(N\)，代表原字符串；

第二行，一个字符串 \(M\)，代表目标字符串；

第三行，四个正整数 \(a,c,g,v\)，分别表示插入一个 A 花费的代价，插入一个 C 花费的代价，插入一个 G 花费的代价，插入一个 T 花费的代价。

输出格式

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

输入输出样例 #1

输入 #1

GTA
CAT
5 7 1 3 

输出 #1

10

输入输出样例 #2

输入 #2

TATA
CACA
3 0 3 0

输出 #2

3

输入输出样例 #3

输入 #3

TCGCGAG
TGCAG
10 10 15 15 

输出 #3

25

说明/提示

【样例解释 #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\)。