Description

The local zoo has obtained a large open garden, where animals can move freely as if in their natural habitat, and entertain visitors with their usual mischief.

The most popular animals are monkeys. With their climbing, jumping, and other tricks, they make visitors happy.

One type of monkey specializes in climbing tall trees and picking coconuts. Another type specializes in cracking them open. There are $n$ monkeys of the first type (numbered $1$ to $n$) and $m$ monkeys of the second type (numbered $1$ to $m$).

For the $k$-th monkey of the first type, it needs $A_k$ seconds to find a good spot in the tree and pick the first coconut. After that, the monkey produces one more coconut every $B_k$ seconds.

For the $k$-th monkey of the second type, it needs $C_k$ seconds to find a good tool to crack coconuts and crack the first coconut. After that, the monkey cracks another coconut every $D_k$ seconds.

Unfortunately, the second type of monkeys is very aggressive, so the two types cannot be in the garden at the same time. Therefore, the zookeeper will drive away the first type of monkeys immediately after they have picked all the coconuts. Similarly, if the same type of monkeys stays too long after cracking all the coconuts, a fight will happen. So the zookeeper will send them away right after they have cracked all the coconuts.

The zookeeper needs to arrive immediately after all coconuts have been picked, and then come back immediately after the monkeys have cracked them all. The time for monkeys to enter or leave the garden is negligible.

Tomislav especially likes the second type of monkeys, but whenever he arrives, he can never see them. Please help him compute the arrival time of the second type of monkeys (he knows the total time the monkeys spend in the garden, but does not know how many coconuts there are).

Input Format

The first line contains an integer $t$, the total time the monkeys spend in the garden, in seconds.

The second line contains an integer $n$, the number of monkeys of the first type.

The next $n$ lines each contain two integers $A_k$ and $B_k$, describing the two parameters of the $k$-th monkey of the first type. See the description for details.

The next line contains an integer $m$, the number of monkeys of the second type.

The next $m$ lines each contain two integers $C_k$ and $D_k$, describing the two parameters of the $k$-th monkey of the second type. See the description for details.

Output Format

Output one integer on a single line, the number of seconds between the arrival of the first type of monkeys and the arrival of the second type of monkeys.

12
1
3 1
1
5 1

5

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

13

Hint

Constraints

For $100\%$ of the testdata, $1 \leq t \leq 1 \times 10^9$, $1 \leq n,m \leq 100$, $1 \leq A_k,B_k,C_k,D_k \leq 1 \times 10^9$.

Notes

Source

Translated from COCI2008-2009 CONTEST #2 SVADA. Translator:

Translated by ChatGPT 5