dist

Să considerăm două propoziţii formate din cuvinte scrise cu litere mari ale alfabetului englez, oricare două cuvinte consecutive fiind separate de unul sau mai multe spaţii.
Să considerăm $c = c_1 \ c_2 \dots c_n$ şi $d = d_1 \ d_2 \dots d_m$ două cuvinte. Pentru a calcula distanţa dintre cuvintele $c$ şi $d$, notată $dist(c, d)$, cuvântul mai scurt se completează la sfârşit cu caracterul @ (care are codul ASCII $64$), până se obţin două cuvinte de aceeaşi lungime, apoi se calculează suma diferenţelor absolute dintre codurile ASCII ale caracterelor situate în cuvintele $c$ şi $d$ pe poziţii corespondente:

$dist(c, d) = |c_1 - d_1| + |c_2 - d_2| + \dots + |c_{lg} - d_{lg}|$, unde $lg = max(n, m)$.

Definim distanţa dintre două propoziţii ca fiind suma distanţelor dintre cuvintele situate în propoziţii pe poziţii corespondente. Dacă una dintre propoziţii are mai puţine cuvinte decât cealaltă se consideră că la sfârşitul acestei propoziţii se află cuvinte vide (cuvinte de lungime $0$), până la completarea numărului necesar de cuvinte.

De exemplu, să considerăm propoziţia $P_1$ = ANA ARE MERE şi propoziţia $P_2$ = VASILE NU. Distanţa dintre propoziţia $P_1$ şi propoziţia $P_2$ este:

$dist(P_1, P_2) = dist("ANA", "VASILE") + dist("ARE", "NU") + dist("MERE","")$.
$dist("ANA","VASILE")$ = $|A - V| + |N - A| + |A - S| + |@ - I| + |@ - L| + |@ - E|$ = $|65 - 86| + |78 - 65| + |65 - 83| + |64 - 73| + |64 - 76| + |64 - 69| = 21 + 13 + 18 + 12 + 9 + 5 = 78$
$dist("ARE","NU")$ = $|A - N| + |R - U| + |E - @|$ = $|65 - 78| + |82 - 85| + |69 - 64| = 13 + 3 + 5 = 21$
$dist("MERE","")$ = $|M - @| + |E - @| + |R - @| + |E - @|$ = $|77 - 64| + |69 - 64| + |82 - 64| + |69 - 64| = 13 + 5 + 18 + 5= 41$.
Deci $dist(P_1, P_2) = 78 + 21 + 41 = 140$

În scopul de a minimiza distanţa dintre cele două propoziţii, asupra celei de a doua propoziţii putem executa una sau mai multe operaţii. O operaţie constă în a muta prima literă dintr-un cuvânt la sfârşitul cuvântului precedent (dacă acesta există) sau ultima literă dintr-un cuvânt la începutul cuvântului următor. Cuvinte vide se pot afla doar la sfârşitul unei propoziţii, nu şi la începutul sau în interiorul ei (nici în propoziţiile date, nici în propoziţiile obţinute în urma aplicării operaţiilor). Cuvintele din propoziţie şi cuvintele obţinute în urma operaţiilor nu pot să depăşească $20$ de litere.

Cerinţă

Să se determine distanţa minimă care se poate obţine între cele două propoziţii efectuând operaţii de tipul celor descrise în enunţ. Se cere de asemenea să se determine şi numărul minim de operaţii ce trebuie să fie executate asupra celei de a doua propoziţii pentru a obţine distanţa minimă.

Date de intrare

Fişierul de intrare dist.in conţine pe prima linie prima propoziţie, iar pe cea de a doua linie a doua propoziţie.

Date de ieșire

Fişierul de ieşire dist.out va conţine o singură linie pe care vor fi scrise două numere naturale separate prin spaţiu $d_{min} \ nr_{min}$, reprezentând în ordine distanţa minimă dintre cele două propoziţii, respectiv numărul minim de operaţii ce trebuie să fie executate asupra celei de a doua propoziţii pentru a obţine distanţa minimă.

Restricții și precizări

• Lungimea totală a unei propoziţii nu depăşeşte $500$ caractere.
• Lungimea maximă a unui cuvânt nu depăşeşte nici în propoziţiile date, nici în propoziţia obţinută în urma aplicării operaţiilor din enunţ $20$ de caractere.
• Numărul maxim de cuvinte dintr-o propoziţie este $100$.
• Se acordă $60\%$ din punctaj pentru determinarea distanţei minime şi $100\%$ pentru rezolvarea ambelor cerinţe.

Exemplu

dist.in

ANA ARE   MERE
VASILE NU

dist.out

62 9

Explicație

Propoziţia a doua, după aplicarea celor $9$ operaţii, este:
V ASI LENU