【题目描述】

给定两个由小写字母组成的字符串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。