时间限制：2000ms　内存限制：512MB

结果比较方式为全文比较（过滤行末空格及文末换行）。

题目描述

某铁路编组站的牵出线上停着一列待编组的货车，每节车厢上标有一个型号字符。当前的车序记为一个字符串 $s$，调度计划要求最终编组顺序为目标字符串 $t$。

调车作业共有四种操作，各自的单位耗时不同：

1. 插入：在任意位置插入一节车厢，耗时为 $A$ 分钟；
2. 删除：摘下一节车厢，耗时为 $B$ 分钟；
3. 替换：把一节车厢换成另一型号的车厢，耗时为 $C$ 分钟；
4. 换位：交换两节相邻车厢的位置，耗时为 $D$ 分钟。

受牵出线长度的限制，原车序中的每一节车厢，在整个调整过程中至多参与一次「删除、替换或换位」（一次换位中的两节车厢各算参与一次；插入的车厢不受此限）。

请计算把 $s$ 调整成 $t$ 所需的最小总耗时。

输入格式

从文件 dist.in 中读入数据。

• 第一行一个字符串 $s$；
• 第二行一个字符串 $t$；
• 第三行四个整数 $A, B, C, D$。

输出格式

输出到文件 dist.out 中。

输出一行一个整数，表示最小总耗时。

样例

样例 1 输入

cat
ct
3 4 6 100

样例 1 输出

4

样例 2 输入

ab
ba
100 100 10 3

样例 2 输出

3

样例 2 解释

交换相邻的 a、b 两节车厢，一次换位后车序即为 ba，耗时 $3$ 分钟。若分别把 a 换成 b、把 b 换成 a，需要 $10+10=20$ 分钟；先摘下一节再插入一节则需 $200$ 分钟。

样例 3 输入

abc
bca
10 10 10 1

样例 3 输出

20

样例 3 解释

先摘下标号为 a 的车厢，耗时 $10$ 分钟，车序变为 bc；再在末尾插入一节 a，耗时 $10$ 分钟，车序变为 bca，总耗时 $20$ 分钟。

若允许同一节车厢反复参与换位，可以先交换 a、b（$1$ 分钟）得到 bac，再交换 a、c（$1$ 分钟）得到 bca，总耗时 $2$ 分钟；但 a 在这两步中参与了两次换位，超出了「每节车厢至多参与一次」的限制，该方案不可行。

数据范围

对于所有测试数据，保证：

• $s$、$t$ 均由小写英文字母构成；
• $1 \le \lvert s\rvert, \lvert t\rvert \le 4000$；
• $1 \le A, B, C, D \le 10^4$。

各测试点的约束如下：

• 特殊性质 A：$D \ge 2C$。
• 特殊性质 B：$t$ 可由 $s$ 的所有字符重新排列得到（两串的字符多重集相同）。