Succes

Se consideră șirul $S=S_1$, $S_2, \dots S_N$ format din $N$ mulțimi de numere naturale cuprinse între $1$ și $M$. De asemenea, se consideră două șiruri de câte $M$ numere întregi $A=A_1$, $A_2, \dots A_M$ și $B=B_1$, $B_2, \dots B_M$.

Numim secvență de mulțimi ($i$, $j$) ($1 \leq i \leq j \leq N$) succesiunea de mulțimi $S_i$, $S_{i+1}, \dots S_j$.

Pentru o secvență de mulțimi ($i$, $j$) ($1 \leq i \leq j \leq N$), se determină factorul de succes pe baza șirului $A$, respectiv factorul de insucces, pe baza șirului $B$ în modul următor:

1. se efectuează reuniunea mulțimilor din secvența de mulțimi $(i, j)$;
2. factorul de succes al secvenței de mulțimi $(i, j)$ este suma valorilor din șirul $A$ situate pe pozițiile date de elementele reuniunii;
3. factorul de insucces al secvenței de mulțimi $(i, j)$ este suma valorilor din șirul $B$ situate pe pozițiile date de elementele reuniunii.

O secvență ($i, j$) ($1 \leq i \leq j \leq N$) este câștigătoare dacă îndeplinește următoarele condiții:

1. factorul de insucces al secvenței este cel mult egal cu un număr natural $K$ dat;
2. factorul de succes al secvenței este cel mai mare dintre factorii de succes corespunzători tuturor secvențelor ce respectă condiția $1$.

Cerință

Determinați factorul de succes al unei secvențe câștigătoare.

Date de intrare

Fișierul de intrare succes.in conține pe prima linie numerele naturale $N$, $M$, $K$.
Pe a doua linie din fișier se găsesc $M$ numere întregi, reprezentând elementele șirului $A$.
Pe a treia linie din fișier se găsesc $M$ numere întregi, reprezentând elementele șirului $B$.
Pe ultimele $N$ linii sunt descrise cele $N$ mulțimi din șirul $S$, câte o mulțime pe o linie. O linie care descrie o mulțime conține $nr$, numărul de elemente din mulțime, urmat de cele $nr$ elemente ale mulțimii.
Valorile scrise pe aceeași linie sunt separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire succes.out conține o singură linie pe care este scris factorul de succes al unei secvențe câștigătoare.

Restricții și precizări

• $1 \leq N \leq 200 \ 000$;
• $1 \leq M \leq 100$;
• Numărul total de elemente din cele $N$ mulțimi este $\leq 1 \ 000 \ 000$;
• $0 \leq K, |{A_i}|, |B_i| \leq 1 \ 000 \ 000 \ 000$, pentru $1 \leq i \leq M$;
• Se garantează că există cel puțin o secvență câștigătoare.

Exemplu

succes.in

4 3 3
3 2 -2
1 2 1
3 1 2 3
2 1 2
1 1
2 3 2

succes.out

5

Explicație

$N=4$, $M=3$, $K=3$.
O secvență câștigătoare este ($2, 3$).
Reuniunea mulțimilor pentru secvența ($2, 3$) este $\{1,2\} \cup \{1\}=\{1,2\}$.
Factorul de insucces pentru secvența ($2, 3$) este $B_1+B_2=1+2=3 \leq K$.
Factorul de succes pentru secvența ($2, 3$) este $A_1+A_2=3+2=5$, valoare maximă pentru toate secvențele pentru care factorul de insucces este $\leq K$.