FMI NO STRESS 12 | Rachete

Gigel se joacă Kerbal Space Program și vrea să construiască o flotă de rachete. O rachetă este formată din $3$ componente: motor, capsulă și echipaj. Acesta știe, pentru fiecare componentă, câte modele există, iar pentru fiecare model de componentă știe câte bucăți sunt disponibile. De asemenea, Gigel vrea să-și testeze capacitățile calculatorului, așa că își impune niște limite cu privire la câte perechi $(\text{model}\:\text{motor},\:\text{model}\:\text{capsulă})$, respectiv $(\text{model}\:\text{capsulă},\:\text{model}\:\text{echipaj})$ se pot găsi în rachetele pe care le construiește (jocul face mult caching dacă se repetă perechile). Dacă o pereche $(\text{model}\: \text{motor},\:\text{model}\: \text{capsulă})$ sau $(\text{model}\: \text{capsulă},\:\text{model}\: \text{echipaj})$ nu apare în lista de limitări, atunci se consideră în mod implicit că perechile de acest tip nu pot apărea în rachete.

Cerință

Gigel vrea să calculeze numărul maxim de rachete pe care le poate construi pentru flota sa.

Date de intrare

Pe prima linie sa găsesc trei numere naturale, $N_1$, $N_2$ și $N_3$, ce reprezintă numărul de modele de motor, capsulă, respectiv echipaj.
Pe a doua linie se găsesc $N_1$ numere naturale, ce reprezintă numărul de bucăți disponibile pentru fiecare model de motor.
Pe a treia linie se găsesc $N_2$ numere naturale, ce reprezintă numărul de bucăți disponibile pentru fiecare model de capsulă.
Pe a patra linie se găsesc $N_3$ numere naturale, ce reprezintă numărul de bucăți disponibile pentru fiecare model de echipaj.
Pe a cincea linie se găsește un număr natural, $M$, ce reprezintă numărul de limitări de perechi.
Pe următoarele $M$ linii se găsesc 4-tupluri de numere naturale $(\text{tip},\:\text{model}_{1},\:\text{model}_{2},\:\text{lim})$, care se interpretează în felul următor:

• dacă $\text{tip}$ este $1$, atunci $\text{model}_1$ este un model de motor, $\text{model}_{2}$ este un model de capsulă, iar numărul maxim de apariții al unei perechi $(\text{model}_{1},\:\text{model}_{2})$ este $\text{lim}$;
• dacă $\text{tip}$ este $2$, atunci $\text{model}_1$ este un model de capsulă, $\text{model}_{2}$ este un model de echipaj, iar numărul maxim de apariții al unei perechi $(\text{model}_{1},\:\text{model}_{2})$ este $\text{lim}$.

Date de ieșire

Pe prima linie se va găsi un singur număr natural, numărul maxim de rachete.

Restricții și precizări

• $1 \leq N_1, N_2, N_3 \leq 150$;
• $1 \leq M \leq 45 \ 000$;
• $1 \leq \text{lim} \leq 1 \ 000$;
• $1 \leq \text{bucăți\_model\_motor} \leq 1 \ 000$;
• $1 \leq \text{bucăți\_model\_capsulă} \leq 1 \ 000$;
• $1 \leq \text{bucăți\_model\_echipaj} \leq 1 \ 000$;
• Pentru teste în valoare de $20$ de puncte:
  • $1 \leq N_1, N_2, N_3 \leq 2$;
  • $1 \leq M \leq 8$;
  • $1 \leq \text{lim} \leq 2$;
  • $1 \leq \text{bucăți\_model\_motor} \leq 3$;
  • $1 \leq \text{bucăți\_model\_capsulă} \leq 3$;
  • $1 \leq \text{bucăți\_model\_echipaj} \leq 3$;
• Pentru restul de $80$ de puncte, nu există restricții suplimentare.

Exemplu

stdin

2 2 1
2 3
3 3
3
5
1 2 2 1
1 1 2 2
2 2 1 2
2 1 1 2
1 1 1 2

stdout

3

Explicație

Se pot construi doar $3$ rachete, o modalitate fiind următoarea (în formatul $(\text{model\_motor}, \text{model\_capsulă}, \text{model\_echipaj})$):

$(2, 2, 1)$
$(1, 2, 1)$
$(1, 1, 1)$