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 BX. 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 BX≥BX-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 containerului în care este depozitată. Suma totală plătită este egală cu suma sumelor plătite pentru fiecare substanţă.
Cerinţă
Determinaţi care este suma totală minimă pe care trebuie să o plătească compania AB pentru a depozita toate substanţele, respectând restricţiile precizate.
Date de intrare
Prima linie a fişierului de intrare ab3.in conţine numărul întreg T, reprezentând numărul de seturi de date ce sunt descrise în continuare. Prima linie a fiecărui set de date conţine 3 numere întregi, separate prin câte un spaţiu: M N K. Următoarea linie conţine K numere întregi, separate prin spaţii. Al P-lea dintre aceste numere reprezintă suma ce trebuie plătită dacă o substanţă este depozitată în al P-lea container. Următoarea linie conţine numărul întreg B1. Următoarele M-1 linii conţin, pentru fiecare acid X de la 2 la M, valorile BX-BX-1 (numărul bazelor “suplimentare” pentru care are afinitate acidul X şi nu are afinitate acidul X-1).
Date de ieşire
În fişierul de ieşire ab3.out veţi afişa T linii. A i-a dintre aceste linii va conţine suma minimă pe care trebuie să o plătească compania AB, considerând informaţiile din al i-lea set de date din fişierul de intrare.
Restricţii
1 ≤ T ≤ 10
1 ≤ M, N ≤ 30000
2 ≤ K ≤ 1000
1 ≤ SP ≤ 1000
Este posibil ca în unele containere să nu fie depozitată nici o substanţă.
50% din fişierele de test vor avea toate valorile M şi N mai mici sau egale cu 2500.
Exemple
ab3.in
ab3.out
Explicaţii
2
4 5 5
4 3 2 1 97
1
0
0
4
1 30000 2
999 1000
0
12
29970999
În 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 obţine suma totală 12 este următoarea: acizii 1, 2 şi 3, precum şi bazele 2, 3, 4 şi 5 sunt depozitate în containerul 4, baza 1 este depozitată în containerul 3, iar acidul 4 în containerul 2.
În cazul celui de-al doilea set de date, acidul 1 nu are afinitate pentru nici o bază. Toate cele 30001 substanţe sunt depozitate în containerul 1.