题目描述

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

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

输入格式

第一行，一个字符串 $N$，代表原字符串；

第二行，一个字符串 $M$，代表目标字符串；

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

输出格式

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

GTA
CAT
5 7 1 3 

10

TATA
CACA
3 0 3 0

3

TCGCGAG
TGCAG
10 10 15 15 

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$。

【来源】

本题分值按 COCI 原题设置，满分 $80$。

题目译自 COCI2013-2014 CONTEST #4 T2 GMO。