助教判斷抄襲的方法

題目敘述

各位應該知道吧，助教在一開始的時候就有說會判斷抄襲了，當然助教判斷抄襲的方法是非常困難的，不過這裡提供一個簡單的版本希望大家能實做出來。

1. 在$A$的任意位置插入一個字符，花費是$c0$
2. 刪除$A$的任意位置的一個字符，花費是$c1$
3. 把$A$的任意位置的一個字符修改成另一字符，花費是$c2$

例如$A="abcde"$，$B="abdefg"$，則$B$可以由$A$刪除字符$'c'$後，再插入字符$'f','g'$到正確的位置這三次轉換變成，總花費為$c1+2*c0$。現在給你$c0,c1,c2$和$A,B$，請你輸出把$A$轉換到$B$所需要的最小總花費。

輸入說明

第一行有三個正整數$c0,c1,c2$，皆大於0且小於等於1000000，接著有多行，不會超過20行，以EOF結尾，每行有兩個字串$A,B$，由小寫字母組成。

輸出說明

對於每組$A,B$，輸出$A$變到$B$的最小花費

範例輸入 1

1 1 1
abcde abdefg
aassjdfghdgdf hlknakjnakjs

範例輸出 1

3
13

範例輸入 2

1 1000 1
abcde abdefg
aassjdfghdgdf hlknakjnakjs

範例輸出 2

4
1012

配分方法

• 0% 範例測資
• 40% $|A|,|B| \leq 100$
• 60% $|A|,|B| \leq 1000$

Hints

備註

Judge Setting