[SDOI2006] 最短距离

一种 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` | `alt` | `rithm` | | `copy r` | `altr` | `ithm` | | `insert u` | `altru` | `ithm` | | `insert i` | `altrui` | `ithm` | | `insert s` | `altruis` | `ithm` | | `twiddle it into ti` | `altruisti` | `hm` | | `replace h to c` | `altruistic` | `m` | | `kill` | `altruistic` | （空） | 要达到这个结果还可能有其它一些操作序列。 操作 delete、replace、copy、insert、twiddle 和kill中每一个都有一个相联系的代价 cost。例如： ```plain 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$ 的非负整数。