centre

Time limit: 0.05s Memory limit: 16MB Input: centre.in Output: centre.out

O recunoscută companie internaţională a deschis în oraş două fabrici de ciocolată şi nn 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 nn 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: nn – numărul de centre, x1x_1 – numărul de cutii cu ciocolată produse de prima fabrică şi x2x_2 – numărul de cutii cu ciocolată produse de a doua fabrică, separate prin câte un spaţiu.
  • Pe a doua linie: nn numere naturale nenule c1,c2,,cnc_1, c_2, \dots, c_n reprezentând cererile celor nn centre de distribuţie; cic_i este numărul de cutii de ciocolată solicitate de centrul de distribuție ii.
  • Pe a treia linie: nn numere naturale nenule reprezentând costurile de transport ale unei cutii de la prima fabrică la fiecare dintre cele nn centre cost1,1,cost1,2,,cost1,ncost_{1, 1}, cost_{1, 2}, \dots, cost_{1, n}.
  • Pe a patra linie: nn numere naturale nenule reprezentând costurile de transport ale unei cutii de la a doua fabrică la fiecare dintre cele nn centre cost2,1,cost2,2,,cost2,ncost_{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 nn centre de distribuţie.

Restricții și precizări

  • 1<n2001 < n \leq 200
  • 1ci201 \leq c_i \leq 20
  • 1<x1,x2<4 0001 < x_1, x_2 < 4 \ 000
  • nx1+x2n \leq x_1 + x_2
  • c1+c2++cn=x1+x2c_1 + c_2 + \dots + c_n = x_1 + x_2
  • 0<costi,j1 0000 < cost_{i, j} \leq 1 \ 000, 1in1 \leq i \leq n, 1jn1 \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 cost1,10+cost1,24+cost1,31+cost2,13+cost2,20+cost2,33=50+24+31+53+30+43=38cost_{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.

Log in or sign up to be able to send submissions!