Kilonova
Toggle theme

FMI NO STRESS 12 | Rachete

This was the problem page during the contest. Access the current page here.
Time limit: 0.4s Memory limit: 64MB Input: Output:

Gigel se joacă Kerbal Space Program și vrea să construiască o flotă de rachete. O rachetă este formată din 33 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 (model motor, model capsula˘)(\text{model}\:\text{motor},\:\text{model}\:\text{capsulă}), respectiv (model capsula˘, model echipaj)(\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 (model motor, model capsula˘)(\text{model}\: \text{motor},\:\text{model}\: \text{capsulă}) sau (model capsula˘, model echipaj)(\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, N1N_1, N2N_2 și N3N_3, ce reprezintă numărul de modele de motor, capsulă, respectiv echipaj.
Pe a doua linie se găsesc N1N_1 numere naturale, ce reprezintă numărul de bucăți disponibile pentru fiecare model de motor.
Pe a treia linie se găsesc N2N_2 numere naturale, ce reprezintă numărul de bucăți disponibile pentru fiecare model de capsulă.
Pe a patra linie se găsesc N3N_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, MM, ce reprezintă numărul de limitări de perechi.
Pe următoarele MM linii se găsesc 4-tupluri de numere naturale (tip, model1, model2, lim)(\text{tip},\:\text{model}_{1},\:\text{model}_{2},\:\text{lim}), care se interpretează în felul următor:

  • dacă tip\text{tip} este 11, atunci model1\text{model}_1 este un model de motor, model2\text{model}_{2} este un model de capsulă, iar numărul maxim de apariții al unei perechi (model1, model2)(\text{model}_{1},\:\text{model}_{2}) este lim\text{lim};
  • dacă tip\text{tip} este 22, atunci model1\text{model}_1 este un model de capsulă, model2\text{model}_{2} este un model de echipaj, iar numărul maxim de apariții al unei perechi (model1, model2)(\text{model}_{1},\:\text{model}_{2}) este lim\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≤N1,N2,N3≤1501 \leq N_1, N_2, N_3 \leq 150;
  • 1≤M≤45 0001 \leq M \leq 45 \ 000;
  • 1≤lim≤1 0001 \leq \text{lim} \leq 1 \ 000;
  • 1≤buca˘ți_model_motor≤1 0001 \leq \text{bucăți\_model\_motor} \leq 1 \ 000;
  • 1≤buca˘ți_model_capsula˘≤1 0001 \leq \text{bucăți\_model\_capsulă} \leq 1 \ 000;
  • 1≤buca˘ți_model_echipaj≤1 0001 \leq \text{bucăți\_model\_echipaj} \leq 1 \ 000;
  • Pentru teste în valoare de 2020 de puncte:
    • 1≤N1,N2,N3≤21 \leq N_1, N_2, N_3 \leq 2;
    • 1≤M≤81 \leq M \leq 8;
    • 1≤lim≤21 \leq \text{lim} \leq 2;
    • 1≤buca˘ți_model_motor≤31 \leq \text{bucăți\_model\_motor} \leq 3;
    • 1≤buca˘ți_model_capsula˘≤31 \leq \text{bucăți\_model\_capsulă} \leq 3;
    • 1≤buca˘ți_model_echipaj≤31 \leq \text{bucăți\_model\_echipaj} \leq 3;
  • Pentru restul de 8080 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 33 rachete, o modalitate fiind următoarea (în formatul (model_motor,model_capsula˘,model_echipaj)(\text{model\_motor}, \text{model\_capsulă}, \text{model\_echipaj})):

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

Log in or sign up to be able to send submissions!