题目描述

一种 EDIT 字母编辑器，它的功能是可以通过不同的变换操作可以把一个源串 $X[l\cdots m]$ 变换为新的目标串 $Y[1\cdots n]$。EDIT 提供的变换操作有：

• 删除源串首个字符（delete）；
• 替换源串首个字符放到目标串末尾（replace）。replace 操作可以替换为与原来相同的字符；
• 移动源串首个字符放到目标串末尾（copy）；
• 向目标串插入单个字符（insert）；
• 交换源串中的两个相邻字符，并移动到目标串末尾中去（twiddle）；
• 在完成其它所有操作之后，源串中余下的全部后缀就可用删至行末的操作删除（kill）。

例如，将源 algorithm 转换成目标串 altruistic 的一种方法是采取下面的操作序列：

操作	目标串	原串
初始	（空）	algorithm
copy a	a	lgorithm
copy l	al	gorithm
replace g to t	alt	orithm
delete o		rithm
copy r	altr	ithm
insert u	altru
insert i	altrui
insert s	altruis
twiddle it into ti	altruisti	hm
replace h to c	altruistic	m
kill		（空）

要达到这个结果还可能有其它一些操作序列。

操作 delete、replace、copy、insert、twiddle 和kill中每一个都有一个相联系的代价 cost。例如：

cost(delete) =3;
cost(replace)=6;
cost(copy)   =5;
cost(insert) =4;
cost(twiddle)=4;
cost(kill) = 被删除的串长 * cost(delete) - 1;

一个给定的操作序列的代价为序列中各操作代价之和。 例如上述操作序列的代价为

$$\begin{aligned}&3\times \mathrm{cost}(\mathtt{copy})+2\times \mathrm{cost}(\mathtt{replace})+\mathrm{cost}(\mathtt{delete})+3\times \mathrm{cost}(\mathtt{insert}) \\ &+\mathrm{cost}(\mathtt{twiddle}) +\mathrm{cost}(\mathtt{kill}) \\ =\ & 3\times 5+2\times 6+3+3\times 4+4+1\times 3-1\\ =\ &48\end{aligned}$$

编程任务

给定两个序列 $X[1\cdots m],Y[1\cdots n]$ 和一些操作代价集合，$X$ 到 $Y$ 的最短距离为将 $X$ 转化为 $Y$ 的最小的转换序列的代价。请给出一个算法来找出 $X[1\cdots m]$ 至 $Y[1\cdots n]$ 的最短距离。

输入格式

第一行：源序列 $X[1\cdots m]$。

第二行：目标序列 $Y[1\cdots n]$。

第三行：$5$ 个正整数，分别是：delete、replace、copy、insert、twiddle 的代价。

输出格式

一行一个整数，表示 $X$ 到 $Y$ 的最短距离（最小代价和）。

algorithm
altruistic
3 6 5 4 4

48

提示

数据范围及约定

对于全部数据，满足 $1\le n,m\le 200$，且所有代价均为不大于 $100$ 的非负整数。