SVADA  Svada
The local zoo has acquired a large open garden in which animals may freely move as in their natural habitats and entertain visitors with their usual shenanigans.
The most popular animals are monkeys. With their climbing and jumping and other skills, they delight old and young visitors alike.
One species of monkey has specialized in climbing tall trees and picking off coconuts. Another species has specialized in breaking them open.
There are N monkeys of the first type (numbered 1 through N) and M monkeys of the second type (numbered 1 through M).
Monkey k of the first type takes Ak seconds to find a good spot on the tree, after which it picks off its first coconut. After that the monkey produces a new coconut every Bk seconds.
Monkey k of the second type takes Ck seconds to find a good tool for opening the coconuts, after which it opens its first coconut. After that the monkey opens another coconut every Dk seconds.
Unfortunately, the second type of monkey is extremely aggressive so the two types may not be in the garden at the same time. Therefore, zoo keepers will chase away the first type of monkeys as soon as they have picked off all the coconuts. Similarly, if monkeys of the same type stay too long after opening all the coconuts, fights will ensue. Because of that, zoo keepers will send them away as soon as they have opened all the coconuts.
The zoo keepers first arrive immediately after all coconuts have been picked, and again immediately after the monkeys open them all. The time needed for monkeys to enter or leave the garden is also negligibly small.
Tomislav especially likes the second type of monkey, but can never guess when to arrive in order to see them. Help him calculate the time when the second type arrives if he knows the total time that monkeys spent in the garden, but does not know the number of coconuts in the garden.
Input
The first line contains the integer T (1 ≤ T ≤ 1 000 000 000), the total time that monkeys spent in the garden, in seconds.
The next line contains the integer N (1 ≤ N ≤ 100), the number of monkeys of the first type.
Each of the following N lines contains two integers Ak and Bk (1 ≤ Ak, Bk ≤ 1 000 000 000), how fast monkey k of the first type is.
The next line contains the integer M (1 ≤ M ≤ 100), the number of monkeys of the second type.
Each of the following M lines contains two integers Ck and Dk (1 ≤ Ck, Dk ≤ 1 000 000 000), how fast monkey k of the second type is.
Output
Output the number of seconds between the arrival of the first type of monkeys and the arrival of the second type.
Example
Input: 20 2 3 2 1 3 3 3 1 4 1 5 1 Output: 13
hide comments
luka_dzimba911:
20180107 16:45:05
Do not trust SPOJ toolkit on this one , spoj toolkit giving WA for some testcases 

kiwi1995:
20160705 14:52:04
ambiguous statement....bt nice one ;)


Vivek Mangal:
20160325 16:58:31
difficult to understand but easy to program if you understand it.


sri:
20151102 14:26:03
anyone explain the testcase.... 

vsri293:
20150527 11:35:18
remember 2nd type of monkey is aggresive !!! 

Petar Bosnjak:
20140403 23:21:19
AC in 1st try :) 

coderred:
20121211 14:12:30
Read.. the question properly


Mrs. Bean:
20120521 15:56:21
please provide some more test cases !!! 

Vaibhav Bahl:
20111229 11:16:59
If you're getting WAs, make sure u have understood the example correctly ;) 
Added by:  Race with time 
Date:  20081116 
Time limit:  0.231s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  COCI 20082009 