P6423 [COCI 2008/2009 #2] SVADA

当地的动物园已经获得了一个大型开放式花园，动物可以像在其自然栖息地中那样随意移动，并以平常的恶作剧来招待游客。 最受欢迎的动物是猴子。随着他们的攀登，跳跃和其他坎，他们使老老游客都感到高兴。 一种猴子专门研究爬高大的树木和摘椰子。另一种专门研究它们的开放性。 有 $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$ 只第二种猴子的两个相关数据，具体解释请参照题目描述。

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

#### 数据规模与约定 对于 $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](https://hsin.hr/coci/archive/2008_2009/) [CONTEST #2](https://hsin.hr/coci/archive/2008_2009/contest2_tasks.pdf) SVADA，译者 @[mnesia](https://www.luogu.com.cn/user/115711)。