You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

【题目描述】

给定两个由小写字母组成的字符串s,t，你可以对s进行以下四种操作：

（1） 在任意位置添加任意一个字母，代价为a。

（2） 删除任意一个字母，代价为b。

（3） 替换任意一个字母，代价为c。

（4） 交换相邻两个字母，代价为d。

你需要求出将s变为t的最小代价。

【输入数据】

第一行四个正整数a,b,c,d。第二行一个字符串s。第三行一个字符串t。

【输出数据】

一行一个整数表示答案。

【样例输入】

1 1 1 1

youshouldnot

thoushaltnot

【样例输出】

5

【数据范围】

对于10%的数据，|s|,|t|<=5。

对于另外30%的数据，保证存在一种最优解不使用操作4。

对于100%的数据，0<|s|,|t|<=4000，0<a,b,c,d<=10000，a+b<=2*d。