当地的动物园新建了一个大型的露天花园，动物们可以在这里像在自然栖息地中一样自由活动，并用它们日常的趣事逗乐游客。
最受欢迎的动物是猴子。凭借攀爬、跳跃等本领，它们给老少游客都带来了欢乐。
其中一种猴子擅长爬上高树采摘椰子。另一种猴子则擅长将椰子砸开。
花园里有 $N$ 只第一种猴子（编号为 $1$ 到 $N$）和 $M$ 只第二种猴子（编号为 $1$ 到 $M$）。
第一种猴子中的第 $k$ 只猴子需要 $A_k$ 秒来在树上找到一个合适的位置，之后它会采摘它的第一个椰子。此后，这只猴子每隔 $B_k$ 秒就会采摘一个新椰子。
第二种猴子中的第 $k$ 只猴子需要 $C_k$ 秒来找到一个合适的工具来打开椰子，之后它会打开它的第一个椰子。此后，这只猴子每隔 $D_k$ 秒就会打开另一个椰子。
不幸的是，第二种猴子极具攻击性，因此这两种猴子不能同时出现在花园里。因此，一旦第一种猴子摘完了所有的椰子，动物园管理员就会把它们赶走。同样地，如果同一种猴子在打开所有椰子后停留太久，就会发生打斗。因此，一旦第二种猴子打开了所有的椰子，管理员就会把它们送走。
管理员在所有椰子被采摘完后立即第一次到达，并在猴子将它们全部打开后再次立即到达。猴子进入或离开花园所需的时间也极短，可以忽略不计。
Tomislav 特别喜欢第二种猴子，但总是猜不准什么时候来才能看到它们。如果他知道猴子在花园里度过的总时间，但不知道花园里椰子的数量，请帮助他计算第二种猴子到达的时间。
输入格式
第一行包含一个整数 $T$（$1 \le T \le 1\,000\,000\,000$），表示猴子在花园里度过的总时间（以秒为单位）。
第二行包含一个整数 $N$（$1 \le N \le 100$），表示第一种猴子的数量。
接下来的 $N$ 行，每行包含两个整数 $A_k$ 和 $B_k$（$1 \le A_k, B_k \le 1\,000\,000\,000$），表示第一种猴子中第 $k$ 只猴子的速度。
下一行包含一个整数 $M$（$1 \le M \le 100$），表示第二种猴子的数量。
接下来的 $M$ 行，每行包含两个整数 $C_k$ 和 $D_k$（$1 \le C_k, D_k \le 1\,000\,000\,000$），表示第二种猴子中第 $k$ 只猴子的速度。
输出格式
输出第一种猴子到达（即花园开放）与第二种猴子到达之间相隔的秒数。
样例
输入 1
12 1 3 1 1 5 1
输出 1
5
输入 2
20 2 3 2 1 3 3 3 1 4 1 5 1
输出 2
13
说明
在第一个样例中，花园里实际上有三个椰子：
- 第一种猴子在花园开放 $3$ 秒后采摘了第一个椰子。
- 该猴子在花园开放 $4$ 秒后采摘了第二个椰子。
- 该猴子在花园开放 $5$ 秒后采摘了第三个椰子。
- 管理员进来并护送该猴子离开。第二种猴子到达。输出为 $5$，因为这就是 Tomislav 想要到达的时间。
- 第二种猴子在花园开放 $10$ 秒后打开了第一个椰子。
- 该猴子在花园开放 $11$ 秒后打开了第二个椰子。
- 该猴子在花园开放 $12$ 秒后打开了第三个椰子。
- 管理员进来并护送该猴子离开。