← 返回题目列表

Codeforces · 67/C

C. 球的顺序

中文机器翻译题面 查看原题

老师给你一系列球 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。