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 \leq X \leq 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 \leq X \leq 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 \geq 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 $S_P$. 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ţă.

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 ab.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$ şi $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 $B_1$. Următoarele $M-1$ linii conţin, pentru fiecare acid $X$ de la $2$ la $M$, valorile $B_X-B_{X-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 ab.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 şi precizări

• $1 \leq T \leq 10$
• $1 \leq M,N \leq 30 \ 000$
• $2 \leq K \leq 1 \ 000$
• $1 \leq SP \leq 1 \ 000$
• 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 $2 \ 500$.

Exemplu

ab.in

2 
4 5 5
4 3 2 1 97
1 
0 
0 
4 
1 30000 2
999 1000
0

ab.out

12
29970999

Explicație

Î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 $30 \ 001$ substanţe sunt depozitate în containerul $1$.