Meil on antud kaks stringi a ja b. Lisaks meil on antud täisarvud D, A, C mis tähistavad vastavalt tähe kustutamise, lisamise ja muutmise hinda.
Kahel stringil a ja b on defineeritud muutmise kaugus (edit distance) kui minimaalne võimalik hind mingil operatsioonide jadal, kus tähe kustutamise, lisamise ja muutmise kaudu muudetakse string a stringiks b. Leia nende stringide muutmiskaugus.
Input
Esimesel real on antud täisarv N(1 ≤ N ≤ 1000)
Teisel real on antud väikestest inglise tähtedest koosnev string a, mille pikkus on N.
Kolmandal real on antud täisarv M(1 ≤ M ≤ 1000)
Neljandal real on antud väikestest inglise tähtedest koosnev string b, mille pikkus on M.
Viiendal real on antud 3 täisarvu D, A ja C(1 ≤ A, B, C ≤ 1000), mis vastavad operatsioonide hindadele.
Output
Väljundi ainsale reale väljasta täisarv mis vastab a ja b muutmiskaugusele.
Sample test(s)
input
18
arandomtextsnippet
16
randtextfilesnip
1 1 1
output
10
Note
Algoritm on kirjeldatud siin: https://en.wikipedia.org/wiki/Wagner–Fischer_algorithm