O recunoscută companie internaţională a deschis în oraş două fabrici de ciocolată şi n centre de distribuţie. Fabricile produc un singur sortiment de ciocolată şi utilizează ca ambalaj un singur model de cutii. Fiind o companie eficientă dar preocupată de reducerea poluării în oraş, pentru livrarea săptămânală a comenzilor la centrele de distribuţie se foloseşte doar o maşină. Au fost estimate costurile de transport a unei cutii cu ciocolată de la fiecare dintre cele două fabrici la fiecare centru. În fiecare săptămână, producţia cumulată a celor două fabrici acoperă exact cererile celor n centre.

Cerința

Scrieţi un program care calculează costul minim de transport săptămânal pentru livrarea comenzilor la cele n centre de distribuţie, cunoscând cantităţile produse de cele două fabrici, cererea fiecărui centru de distribuţie şi costurile de transport ale unei cutii cu ciocolată de la fiecare fabrică la fiecare centru.

Date de intrare

Fișierul de intrare centre.in Fişierul de intrare centre.in conţine:

• pe prima linie: n – numărul de centre, x1 – numărul de cutii cu ciocolată produse de prima fabrică şi x2 – numărul de cutii cu ciocolată produse de a doua fabrică, separate prin câte un spaţiu.
• Pe a doua linie: n numere naturale nenule c[1] c[2] … c[n] reprezentând cererile celor n centre de distribuţie, c[i] = numar de cutii de ciocolată solicitate de centrul de distribuție i.
• Pe a treia linie: n numere naturale nenule reprezentând costurile de transport ale unei cutii de la prima fabrică la fiecare dintre cele n centre cost[1][1] cost[1][2] … cost[1][n].
• Pe a patra linie: n numere naturale nenule reprezentând costurile de transport ale unei cutii de la a doua fabrică la fiecare dintre cele n centre cost[2][1] cost[2][2] … cost[2][n].

Date de ieșire

Fișierul de ieșire centre.out va conţine o singură linie pe care va fi scris un număr natural care reprezintă costul minim de transport săptămânal, pentru satisfacerea tuturor cererilor celor n centre de distribuţie.

Restricții și precizări

• 1 < n ≤ 200, 1 ≤ c[i] ≤ 20, 1 < x1, x2 < 4000, n ≤ x1 + x2
• c[1] + c[2] + … + c[n] = x1 + x2
• 0 < cost[i][j] ≤ 1000, 1 ≤ i ≤ n, 1 ≤ j ≤ n

Exemplu:

centre.in

3 5 6
3 4 4 
5 2 3
5 3 4 

centre.out

38

Explicație

O posibilă soluţie ar fi
cost[1][1]*0 + cost[1][2]*4 + cost[1][3]*1 + cost[2][1]*3 + cost[2][2]*0 + cost[2][3]*3 =
5 * 0 + 2 * 4 + 3 * 1 + 5 * 3 + 3 * 0 + 4 * 3 = 38.