Flămânzilă

Flămânzilă, fiind pasionat de arta culinară, precum și de matematică, și-a propus să facă sandwich-ul perfect. Acesta își așează ingredientele sub forma unei matrici $A$ cu $N$ linii și $M$ coloane, fiecare ingredient fiind reprezentat de o literă mică a alfabetului englez. El alege și o rețetă cu $N + M - 1$ ingrediente, notată sub forma unui șir de litere mici $R$. Acesta poate alege diverse drumuri care încep de pe poziția $(1,1)$ și se termină pe poziția $(N,M)$, unde la fiecare pas are posibilitatea să meargă fie la dreaptă, fie în jos. Formal, dacă el inițial se află pe poziția $(x,y)$, atunci Flămânzilă, poate să se deplaseze fie la poziția $(x + 1, y)$, fie la $(x, y+1)$, asta dacă nu iese din matrice.

Flămânzilă compară ingredientele pe un drum corect ales de el cu ingredientele din rețeta lui și stabilește un coeficient de similitudine egal cu suma valorilor absolute a diferențelor dintre codurile ASCII ale ingredientelor corespunzătoare. De exemplu, dacă pe un drum în matrice avem ingredientele $a,b,e,d,t$, iar reteta este $a,c,e,f,t$, atunci coeficientul de similitudine este: $|a – a| + |b – c| + |e – e| + |f – d| + |t – t| = 0 + 1 + 0 + 2 + 0 = 3$.

Cerinta

Dată fiind matricea $A$ cu $N$ linii și $M$ coloane, precum și șirul de caractere $R$ de lungime $N + M - 1$, găsiți valoarea minimă coeficientul de similitudine dintre un drum în matrice și rețeta $R$.

Date de intrare

Fișierul de intrare flamanzila.in conține pe prima linie două numere naturale, $N$ și $M$, reprezentând numărul de linii și de coloane ale matricii. Pe următoarele $N$ linii se află câte un șir cu exact $M$ caractere, iar pe ultima linie a fișierului se găsește șirul de litere $R$ de lungime $N + M – 1$.

Date de iesire

În fișierul de ieșire flamanzila.out se găsește răspunsul la problemă, adică coeficientul minim de similitudine posibil între un drum din matricea $A$ și rețeta $R$.

Restrictii si precizari

• $1 \le N, M \le 1 \ 000$

Exemplu

flamanzila.in

3 3
abc 
ced
qrt 
aceft 

flamanzila.out

2

Explicatie

Putem alege drumul $(1, 1),(2, 1),(2, 2),(2, 3),(3, 3)$, rezultatul fiind $|a−a|+|c−c|+|e−e|+|d−f|+|t−t| = 0 + 0 + 0 + 2 + 0 = 2$.