老师给你一系列球 A,每个球都标有小写拉丁字母“a”-“z”。您不喜欢给定的顺序。你想把它改成更适合你的新序列B。因此,您允许自己进行四种操作:
- 您可以将带有任何标签的任何球插入序列中的任何位置。
- 您可以从任何位置删除(移除)任何球。
- 您可以用任何其他球替换任何球。
- 您可以交换(交换)两个相邻的球。
您的老师现在对每个操作都设置了时间限制,这意味着操作只能在特定时间内执行。因此,第一个操作需要时间 ti,第二个操作需要 td,第三个操作需要 tr,第四个操作需要 te。另外,还给出2·te ≥ ti + td。
求将序列 A 转换为序列 B 的最短时间。
输入
第一行包含四个空格分隔的整数 ti, td, tr, te (0 < ti, td, tr, te ≤ 100)。以下两行在不同的行上包含序列 A 和 B。每行的长度在 1 到 4000 个字符之间(含 1 和 4000 个字符)。
输出
打印一个整数,表示将 A 转换为 B 的最短时间。
示例
输入 #1
1 1 1 1 youshouldnot thoushaltnot
输出 #1
5
输入 #2
2 4 10 3 ab ba
输出 #2
3
输入 #3
1 10 20 30 a za
输出 #3
1
注意
在第二个示例中,您可以从第一个位置删除标记为“a”的球,然后在新的第二个位置插入另一个“a”,总时间为 6。但是,交换球的总时间为 3。