Zoo

Cerința

Grădina zoologică locală a dobândit o grădină mare deschisă, în care animalele se pot mișca liber ca în habitatele lor naturale și pot să distreze vizitatorii cu giumbușlucurile lor obișnuite.
Cele mai apreciate animale sunt maimuțele. Cu abilitățile lor de cățărat, sărituri și altele( :) ), îi încântă deopotrivă pe vizitatorii bătrâni și pe cei tineri.

O specie de maimuță s-a specializat în cățăratul în copaci înalți și în culegerea nucilor de cocos. O altă specie s-a specializat în spargerea lor.
Sunt $N$ maimuțe de primul tip (numerotate de la $1$ la $N$) și $M$ maimuțe de al doilea tip (numerotate de la $1$ la $M$).

Maimuţa $k$ de primul tip are nevoie de $A_k$ secunde pentru a găsi un loc bun pe copac, de unde culege prima nucă de cocos. După aceea, maimuța culege câte o nucă de cocos nouă la fiecare $B_k$ secunde.
Maimuţa $k$ de al doilea tip are nevoie de $C_k$ secunde pentru a găsi o unealta bună pentru deschiderea nucilor de cocos, după care deschide prima nucă de cocos. După aceea, maimuța deschide câte o nucă de cocos la fiecare $D_k$ secunde.

Din păcate, cel de-al doilea tip de maimuță este extrem de agresiv, așa că nu este posibil ca cele două tipuri să fie în grădină în același timp. Prin urmare, îngrijitorii grădinii zoologice vor alunga primul tip de maimuțe îndată ce au cules toate nucile de cocos. În mod similar, dacă maimuțele de al doilea tip stau prea mult timp după deschiderea tuturor nucilor de cocos, vor avea loc lupte între clanurile mafiote de maimuțe. Din această cauză, îngrijitorii grădinii zoologice le vor scoate din gradină imediat după ce au deschis toate nucile de cocos.

Îngrijitorii grădinii zoologice ajung mai întâi imediat după ce toate nucile de cocos au fost culese și din nou imediat după ce maimuțele le deschid pe toate. Timpul necesar pentru ca maimuțele să intre sau să iasă din grădină este, de asemenea, neglijabil de mic.

Lui Tomiță îi place în mod special al doilea tip de maimuță, dar nu poate ghici niciodată când să ajungă pentru a le vedea. Ajută-l să calculeze ora la care sosește al doilea tip dacă știe timpul total petrecut de către maimuțe în grădină(timpul total al ambelor tipuri), dar nu știe numărul de nuci de cocos din grădină.

Notă: Datele de intrare se citesc de la tastatură, iar datele de ieșire se afișează în consolă.

Date de intrare

Prima linie de intrare conține numărul natural $T$, timpul total petrecut de maimuțe in grădină.
A doua linie de intrare conține numărul natural $N$, numărul de maimuțe de primul tip.
Urmatoarele $N$ linii de intrare conțin perechea de numere naturale $A_k \ B_k$, reprezentând vitezele maimuțelor de primul tip.
Urmatoarea linie de intrare conține numărul natural $M$, numărul de maimuțe de cel de-al doilea tip.
Urmatoarele $M$ linii de intrare conțin perechea de numere naturale $C_k \ D_k$, reprezentând vitezele maimuțelor de cel de-al doilea tip.

Date de ieșire

Afișați pe prima linie numărul de secunde între venirea primului tip de maimuțe și venirea celui de-al doilea tip de maimuțe.

Restricții și precizări

• $1 \le T \le 10^9$
• $1 \le N, M \le 100$
• $1 \le A_k, B_k, C_k, D_k \le 10^9$
• Pentru 60 de puncte, $T \le 1000$.

Exemplu 1

stdin

12
1
3 1
1
5 1

stdout

5

Exemplu 2

stdin

20
2
3 2
1 3
3
3 1
4 1
5 1

stdout

13