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$).

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 afişa $T$ linii. A $i$-a dintre aceste linii va contine suma minima pe care trebuie sa o platească compania AB, considerand informaţiile din al $i$-lea set de date din fisierul de intrare.

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 informaţiile din al $i$-lea set de date din fisierul de intrare.

h2. Restrictii si precizaro

* $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$ ÅŸi $N$ mai mici sau egale cu $2.500$.

* $50%$ din fisierele de test vor avea toate valorile $M$ si $N$ mai mici sau egale cu $2.500$.

h2. Exemplu

h3. Explicatii

In cazul primului set de date, acizii 1, 2 şi 3 au afinitate pentru baza 1, iar acidul 4 are afinitate pentru toate cele 5 baze. O modalitate de a obtine suma totală 12 este urmatoarea: acizii 1, 2 şi 3, precum si bazele 2, 3, 4 şi 5 sunt depozitate in containerul 4, baza 1 este depozitata in containerul 3, iar acidul 4 in containerul 2.

In cazul primului set de date, acizii 1, 2 �i 3 au afinitate pentru baza 1, iar acidul 4 are afinitate pentru toate cele 5 baze. O modalitate de a obtine suma total� 12 este urmatoarea: acizii 1, 2 �i 3, precum si bazele 2, 3, 4 �i 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.