== include(page="template/taskheader" task_id="ab") ==
Compania farmaceutică AB produce substanţe ce fac parte din două categorii: Acizi şi Baze. Ea produce $M$ acizi şi $N$ baze. Acizii sunt numerotaţi de la $1$ la $M$, iar bazele sunt numerotate de la $1$ la $N$.
Unii acizi au o afinitate pentru unele baze. Dacă un acid este pus împreună cu o bază pentru care are afinitate, se produce o reacÅ£ie chimică foarte periculoasă. Doi acizi puÅŸi împreună nu produc nici o reacÅ£ie ÅŸi nici două baze puse împreună. Fiecare acid $X (1 ≤ X ≤ M)$ are afinitate pentru fiecare din bazele numerotate cu numere de la $1$ la $B{~X~}$. Acizii au o proprietate interesantă, datorată faptului că acidul $X (2 ≤ X ≤ M)$ este produs ca urmare a rafinării compoziÅ£iei acidului $X-1$. Astfel, dacă acidul $X-1$ are afinitate pentru fiecare bază dintr-o mulÅ£ime $Q$, atunci ÅŸi acidul $X$ are afinitate pentru fiecare dintre bazele din mulÅ£imea $Q$. Altfel spus, bazele pentru care are afinitate acidul $X-1$ reprezintă o submulÅ£ime a bazelor pentru care are afinitate acidul $X$. Aceasta implică inegalitatea $B{~X~}≥B{~X~}-1$.
Compania are la dispozitie $K$ containere şi fiecare dintre cele $M+N$ substanţe trebuie depozitată într-unul dintre aceste containere. Două substanţe pot fi depozitate în acelaşi container cu condiţia ca ele să nu reacţioneze una cu alta. Depozitarea uneia dintre cele $M+N$ substanţe în al $P$-lea container presupune plata unei sume SP. Aşadar, pentru fiecare substanţă, trebuie plătită suma corespunzătoare container-ului în care este depozitată. Suma totală plătită este egală cu suma sumelor plătite pentru fiecare substanţă.
== include(page="template/badtests") ==
Compania farmaceutica AB produce substante ce fac parte din doua categorii: Acizi si Baze. Ea produce $M$ acizi si $N$ baze. Acizii sunt numerotati de la $1$ la $M$, iar bazele sunt numerotate de la $1$ la $N$.
Unii acizi au o afinitate pentru unele baze. Daca un acid este pus impreuna cu o baza pentru care are afinitate, se produce o reactie chimica foarte periculoasa. Doi acizi pusi impreuna nu produc nici o reactie si nici doua baze puse impreuna. Fiecare acid $X (1 ≤ X ≤ M)$ are afinitate pentru fiecare din bazele numerotate cu numere de la $1$ la $B{~X~}$. Acizii au o proprietate interesanta, datorata faptului ca acidul $X (2 ≤ X ≤ M)$ este produs ca urmare a rafinarii compozitiei acidului $X - 1$. Astfel, daca acidul $X - 1$ are afinitate pentru fiecare baza dintr-o multime $Q$, atunci si acidul $X$ are afinitate pentru fiecare dintre bazele din multimea $Q$. Altfel spus, bazele pentru care are afinitate acidul $X - 1$ reprezinta o submultime a bazelor pentru care are afinitate acidul $X$. Aceasta implica inegalitatea $B{~X~} ≥ B{~X - 1~}$.
Compania are la dispozitie $K$ containere si fiecare dintre cele $M + N$ substante trebuie depozitata intr-unul dintre aceste containere. Doua substante pot fi depozitate in acelasi container cu conditia ca ele sa nu reactioneze una cu alta. Depozitarea uneia dintre cele $M + N$ substante in al $P$-lea container presupune plata unei sume $S{~P~}$. Asadar, pentru fiecare substanta, trebuie platita suma corespunzatoare containerului in care este depozitata. Suma totala platita este egala cu suma sumelor platite pentru fiecare substanta.
Determinati care este suma totala minima pe care trebuie sa o plateasca compania AB pentru a depozita toate substantele, respectand restrictiile precizate.
h2. Date de intrare
...
Prima linie a fisierului de intrare contine numarul intreg $T$, reprezentand numarul de seturi de date ce sunt descrise in continuare. Prima linie a fiecarui set de date contine $3$ numere intregi, separate prin cate un spatiu: $M$, $N$ si $K$. Urmatoarea linie contine $K$ numere intregi, separate prin spatii. Al $P$-lea dintre aceste numere reprezinta suma ce trebuie platita daca o substanta este depozitata in al $P$-lea container. Urmatoarea linie contine numarul intreg $B{~1~}$. Urmatoarele $M-1$ linii contin, pentru fiecare acid $X$ de la $2$ la $M$, valorile $B{~X~} - B{~X-1~}$ (numarul bazelor "suplimentare" pentru care are afinitate acidul $X$ si nu are afinitate acidul $X - 1$).
h2. Date de iesire
...
In fisierul de iesire veti afisa $T$ linii. A $i$-a dintre aceste linii va contine suma minima pe care trebuie sa o plateasca compania AB, considerand informatiile din al $i$-lea set de date din fisierul de intrare.
h2. Restrictii
h2. Restrictii si precizari
* $... ≤ ...$
* $1 ≤ T ≤ 10$
* $1 ≤ M, N ≤ 30.000$
* $2 ≤ K ≤ 1.000$
* $1 ≤ S{~P~} ≤ 1000$
* Este posibil ca in unele containere sa nu fie depozitata nici o substanta.
* $50%$ din fisierele de test vor avea toate valorile $M$ si $N$ mai mici sau egale cu $2.500$.
h2. Exemplu
table(example). |_. ab.in |_. ab.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 2
4 5 5
4 3 2 1 97
1
0
0
4
1 30000 2
999 1000
0
| 12
29970999
|
h3. Explicatie
h3. Explicatii
In cazul primului set de date, acizii 1, 2 si 3 au afinitate pentru baza 1, iar acidul 4 are afinitate pentru toate cele 5 baze. O modalitate de a obtine suma totala 12 este urmatoarea: acizii 1, 2 si 3, precum si bazele 2, 3, 4 si 5 sunt depozitate in containerul 4, baza 1 este depozitata in containerul 3, iar acidul 4 in containerul 2.
In cazul celui de-al doilea set de date, acidul 1 nu are afinitate pentru nici o baza. Toate cele 30001 substante sunt depozitate in containerul 1.
...
== include(page="template/taskfooter" task_id="ab") ==
