题目描述

有两个字符串 $A, B$，每次可以对 $A$ 进行 $4$ 种操作：

1. 插入一个字符，花费 $t_i$ 元；
2. 删除一个字符，花费 $t_d$ 元；
3. 替换一个字符，花费 $t_r$ 元；
4. 交换相邻的两个字符，花费 $t_e$ 元。

保证费用都是 $[1, 100]$ 之间的正整数，且 $2t_e\geq t_i + t_d$。

求将 $A$ 变成 $B$ 最少需要多少元。

输入格式

第一行四个整数 $t_i, t_d, t_r, t_e$。

接下来两行，每行一个字符串分别表示 $A, B$，保证它们长度都不超过 $4000$。

输出格式

一行一个整数表示最小费用。

1 1 1 1
youshouldnot
thoushaltnot

5

2 4 10 3
ab
ba

3

1 10 20 30
a
za

1