编程题：贪心算法

当地动物园获得了一个大型开放式花园，动物可以像在自然栖息地一样自由活动，并用它们惯常的恶作剧来招待游客。

最受欢迎的动物是猴子。凭借他们的攀爬、跳跃和其他技能，他们让老游客和年轻游客都很开心。

有一种猴子擅长爬树和摘椰子。另一个物种专门砸开它们。

第一类猴子有N只（编号1至N），第二类猴子有M只（编号1至M）。

第一种类型的猴子k需要Ak秒在树上找到一个好的位置，然后摘下它的第一个椰子。之后，猴子每Bk秒摘一个新椰子。

第二种类型的猴子k花了Ck秒找到一个打开椰子的好工具，然后打开第一个椰子。之后，猴子每Dk秒摘一个椰子。

不幸的是，第二种猴子非常好斗，所以这两种猴子可能不会同时出现在花园里。因此，动物园管理员会在第一类猴子摘下所有椰子后立即将它们赶走。同样，如果同一类型的猴子在打开所有椰子后停留太久，就会发生争斗。因此，动物园管理员会在他们打开所有的椰子后立即将他们送走。

动物园管理员首先在摘完所有的椰子后立即赶到，然后在猴子们把椰子全部打开后立即赶走。猴子进出花园所需的时间也可以忽略不计。

托米斯拉夫特别喜欢第二种猴子，但他永远猜不到什么时候能看到它们。他知道猴子在花园里待的总时间，但不知道花园里有多少椰子，请帮助他计算第二类猴子到达的时间。

### 输入格式:
第一行包含整数$$T（1≤T≤1000）$$，猴子在花园里的总时间，以秒为单位。

下一行包含整数$$N（1≤N≤100）$$，第一类猴子的数量。

以下$$N$$行中的每一行都包含两个整数$$Ak$$和$$Bk（1≤ Ak，Bk≤1 000 000 000）$$表示第一种的猴子$$k$$的速度。

下一行包含整数$$M（1≤M≤100）$$，第二类猴子的数量。

以下$$M$$行中的每一行都包含两个整数$$Ck$$和$$Dk（1≤Ck，Dk≤1 000 000 000）$$表示第二种的猴子$$k$$的速度。

### 输出格式:
输出第一只猴子到达和第二只猴子到达中间间隔的秒数。

### 输入样例1:
in
12
1
3 1
1
5 1


### 输出样例1:
out
5


### 输入样例2:
in
20
2
3 2
1 3
3
3 1
4 1
5 1


### 输出样例2:
out
13


在第一个例子中，花园里有三个椰子：

•第一种猴子在花园开放3秒钟后摘下第一颗椰子。
•花园开放4秒后，猴子摘下第二个椰子。
•花园开放5秒后，猴子摘下第三个椰子。
•动物园管理员进来护送猴子出去。第二种猴子来了。输出为5，因为这是Tomislav想要到达的时间。
•第二种猴子在花园开放10秒后打开第一个椰子。
•花园开放11秒后，猴子打开第二个椰子。
•花园开放12秒后，猴子打开第三个椰子。
•动物园管理员进来护送猴子出去。






答案：若无答案欢迎评论