题目描述

当地的动物园已经获得了一个大型开放式花园，动物可以像在其自然栖息地中那样随意移动，并以平常的恶作剧来招待游客。

最受欢迎的动物是猴子。随着他们的攀登，跳跃和其他坎，他们使老老游客都感到高兴。

一种猴子专门研究爬高大的树木和摘椰子。另一种专门研究它们的开放性。 有 $n$ 只第一种猴子（编号 $1$ 到 $n$）和 $m$ 种第二种猴子（编号 $1$ 到 $m$）。

第一种猴子的第 $k$ 只需要 $A_k$ 秒才能在树上找到一个好地方，然后摘下第一个椰子。之后，猴子每 $B_k$ 秒产生一个新的椰子。

第二种猴子的第 $k$ 只需要 $C_k$ 秒的时间才能找到打开椰子的好工具，然后打开第一个椰子。之后，猴子每 $D_k$ 秒打开另一个椰子。

不幸的是，第二种猴子非常具有攻击性，因此这两种类型可能不会同时出现在花园中。因此，动物园管理员会在第一类猴子摘下所有椰子后立刻赶走它们。类似地，如果打开所有椰子后，相同类型的猴子停留时间过长，则会发生争斗。因此，动物园管理员将在它们打开所有椰子后将它们送走。

动物园管理员需要在所有椰子都被采摘后立即到达，然后在猴子将它们全部打开后立即返回。猴子进入或离开花园所需的时间也很小。

Tomislav 特别喜欢第二种猴子，但到来时总是看不见它们。请帮助他计算第二种猴子到达的时间（他知道猴子在花园里度过的总时间，但不知道花园里椰子的数量）。

输入格式

第一行一个整数 $t$，表示猴子在花园中度过的总时间，以秒为单位。

第二行一个整数 $n$，表示第一种猴子的只数。

以下 $n$ 行，每行两个整数 $A_k$ 和 $B_k$，表示第 $k$ 只第一种猴子的两个相关数据，具体解释请参照题目描述。

接下来一行一个整数 $m$，表示第二种猴子的只数。

以下 $m$ 行，每行两个整数 $C_k$ 和 $D_k$，表示第 $k$ 只第二种猴子的两个相关数据，具体解释请参照题目描述。

输出格式

一行一个整数，表示第一种猴子到来到第二种猴子到来之间的秒数。

12
1
3 1
1
5 1

5

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

13

提示

数据规模与约定

对于 $100\%$ 的数据，有 $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$。

说明

题目译自 COCI2008-2009 CONTEST #2 SVADA，译者

https://www.luogu.com.cn/user/115711