Se ştie că un subşir al unui şir se obţine eliminând zero, unul, sau mai multe elemente din şirul iniţial. Un subşir comun a două şiruri este subşir atât pentru primul, cât şi pentru al doilea şir.

Să considerăm două şiruri de numere naturale x = x₁, x₂, ..., x_M şi y = y₁, y₂, ..., y_N care au cel puţin un subşir comun. Printre subşirurile comune există cel puţin unul maximal. De exemplu, şirurile 5,3,2 şi 7,3,5,2 au trei subşiruri comune maximale: primul este 5, 2, al doilea 3,2, iar al treilea este 5, 3. Pentru fiecare subşir comun maximal s = s₁, s₂, ..., s_k calculăm costul subşirului astfel: pentru fiecare element si (1 <= i <= k) cost(s_i) = s_i *|p_i – q_i|, unde p_i şi q_i sunt poziţiile unde se află si în şirurile x şi respectiv y, iar |p_i – q_i| este valoarea absolută a diferenţei p_i – q_i. Costul subşirului maximal este suma costurilor elementelor subşirului, deci cost(s) = cost(s₁) + cost(s₂) + ... + cost(s_k). Pentru exemplul de mai sus, subşirul 5, 2 are costul 5 * |3 - 1| + 2 * |4 - 3| = 12.

Cerinţă

Să se determine costul minim al unui subşir comun maximal.

Date de intrare

Fişierul de intrare comun.in conţine pe prima linie, separate printr-un spaţiu, numerele naturale M şi N, reprezentând lungimile celor două şiruri. Pe linia a doua se află M numere separate prin câte un spaţiu, reprezentând elementele primului şir. Pe linia a treia se află N numere separate prin câte un spaţiu reprezentând elementele celui de-al doilea şir.

Date de ieşire

Fisierul de iesire comun.out va conţine o singură linie, pe care va fi scris un singur număr natural reprezentând costul minim al unui subşir comun maximal.

Restricţii

• 3 <= M, N <= 90
• Elementele celor două şiruri sunt numere naturale cuprinse între 1 şi 100
• Cele două şiruri conţin cel puţin un subşir comun nevid

Exemple

comun.in	comun.out	Explicaţii
3 4 5 3 2 7 3 5 2	2	Sunt doua subşiruri comune maximale: 5, 2 având costul 5 * |3 - 1| + 2 * |4 - 3| = 12 3, 2 având costul 3 * |2 – 2| + 2 * |4 – 3| = 2 Costul minim este 2.
comun.in	comun.out	Explicaţii
6 7 1 2 3 5 4 9 4 1 4 3 2 7 9	13	Sunt 3 subşiruri maximale: 1, 2, 9 având costul 1*1 + 2*3 + 9*1 = 16 1, 3, 9 având costul 1*1 + 3*1 + 9*1 = 13 1, 4, 9 având costul 1*1 + 4*2 + 9*1 = 18 Costul minim este 13 şi aparţine celui de-al doilea subşir.

prof. Dan Pracsiu

Grup Scolar „Stefan Procopiu” Vaslui

dpracsiu@yahoo.com