CF67C Sequence of Balls

有两个字符串 $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$。

一行一个整数表示最小费用。 感谢 @C20191629 提供的翻译

In the second sample, you could delete the ball labeled 'a' from the first position and then insert another 'a' at the new second position with total time 6. However exchanging the balls give total time 3.