Fișierul intrare/ieșire	similar.in, similar.out	Sursă	ad-hoc
Autor	din folclor	Adăugată de	Andreescu Mihai • mihai995
Timp de execuție pe test	0.2 sec	Limită de memorie	32768 KB
Scorul tău	N/A	Dificultate	2

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Similar

Marcel are un seif a cărui cheie este un șir de caractere care conține numai caractere mici ale alfabetului englez. Gigel vrea să-i spargă seiful. Marcel știe asta, așa că a pus un dispozitiv care blochează orice tentativă de deschidere a seifului dacă cheia a fost introdusă greșit.
Într-o zi, însă, a tastat greșit cheia, iar seiful s-a blocat. Pentru a evita astfel de situații, Marcel a mai adăugat o regulă: o tastare se consideră greșită doar dacă gradul de similitudine al cheii introduse este mai mare de o anumită valoare. El poate comite următoarele greșeli: poate tasta o altă literă sau poate lovi mai multe taste simultan, adăugând caractere în plus. Deoarece unele erori sunt mai probabile decât altele, Marcel a definit o penalizare pentru fiecare dintre aceste erori, în funcție de poziția la care s-a produs. Gradul de similitudine este suma acestor penalizări.

Cerință

Pentru o cheie introdusă, cheia corectă penalizările de inserare și schimbare ale fiecărui caracter, să se determine cel mai mic grad de similitudine care se obține.

Date de intrare

Fișierul de intrare similar.in va conține pe prima linie cheia introdusă A, pe a doua linie cheia corectă B, pe a treia linie penalizările la ștergere, iar pe a patra linie, penalizările de modificare. Al i-lea element al unei linii cu penalizările de ștergere sau modificare caracterizează al i-lea element al sirului introdus.

Date de ieșire

În fișierul de ieșire similar.out va conține un singur număr, reprezentând similitudinea minimă a celor două șiruri.

Restricții

• $ 1 ≤ |A|, |B| ≤ 2000
• $ 0 ≤ penalizare ≤ 2000000000

Exemplu

Explicație

Se vor elimina primele 2 caractere, ultimele 3 caractere, iar m se va schimba în n, obținând un cost total de 1 + 0 + 1 + 4 + 2 + 2 = 10