centre

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ță

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 conţine:

• Pe prima linie: $n$ – numărul de centre, $x_1$ – numărul de cutii cu ciocolată produse de prima fabrică şi $x_2$ – 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, \dots, c_n$ reprezentând cererile celor $n$ centre de distribuţie; $c_i$ este numărul 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}, \dots, 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}, \dots, 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 \leq 200$
• $1 \leq c_i \leq 20$
• $1 < x_1, x_2 < 4 \ 000$
• $n \leq x_1 + x_2$
• $c_1 + c_2 + \dots + c_n = x_1 + x_2$
• $0 < cost_{i, j} \leq 1 \ 000$, $1 \leq i \leq n$, $1 \leq j \leq 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} \cdot 0 + cost_{1, 2} \cdot 4 + cost_{1, 3} \cdot 1 + cost_{2, 1} \cdot 3 + cost_{2, 2} \cdot 0 + cost_{2, 3} \cdot 3 = 5 \cdot 0 + 2 \cdot 4 + 3 \cdot 1 + 5 \cdot 3 + 3 \cdot 0 + 4 \cdot 3 = 38$.