该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

在学中验实桥杜信奥集训队中，一共有 $n + m$ 名学生，其中有 $n$ 名学生是魔丸，$m$ 名学生是灵珠。

• 魔丸类型的第 $k$ 只学生会在来到机房后的第 $a_k$ 秒打开一台计算机。之后他每 $b_k$ 秒都会打开一台计算机。

• 灵珠类型的第 $k$ 只学生会在来到机房后的第 $c_k$ 秒关闭一台计算机。之后他每 $d_k$ 秒都会关闭一台计算机。

已知机房内的计算机一开始均为关闭，学生只能开启关闭着的计算机，也只能关闭开启着的计算机。

由于灵珠和魔丸互不相容，因此他们不会同时出现在机房。所有的魔丸类型学生会先来到机房，然后按照刚刚给出的方式进行开机。

但是机房管理员 Gooby 不希望开过多的机子，他会在魔丸类型的学生开完适量的机子后将他们赶走，赶走后的瞬间召唤所有灵珠类型的学生来到机房，并且按照上述方式将开启的机子关掉，直到时间消耗完毕。

由于学中验实桥杜幅员辽阔，因此有 $114514^{1919810}$ 台机子可以开。所以魔丸不用担心没有机子可开的情况。

但是如果机房内只有灵珠，并且没有机子可以关时，灵珠就会开始变异并破坏机房，这也是 Gooby 不愿意看到的事情。

因此 Gooby 要选择好进机房的时间点，使得在这之后灵珠不会变异（即要开足够的机子让他们关机）。

Gooby 只知道，灵珠和魔丸在机房总共呆了 $t$ 秒，请你告诉他合适的进场时机。

输入输出格式

输入格式

第一行输入一个整数 $t$ ，表示学生呆的总时间。

第二行输入一个整数 $n$ ，表示魔丸的人数。

接下来 $n$ 行，第 $i$ 行输入两个空格隔开的整数 $a_i, b_i$，表达意义见题意。

接下来一行输入一个整数 $m$，表示灵珠的人数。

接下来 $m$ 行，第 $i$ 行输入两个空格隔开的整数 $c_i, d_i$，表达意义见题意。

输出格式

输出一个整数，表示 Gooby 选择进入机房的时间，如果有多个这样的时间，请输出最早的时间点。

样例

12
1
3 1
1
5 1

5

样例1解释

所有魔丸在 $0$ 时刻来到机房，然后到 $t = 3$ 时开启了第一台机子，之后一直到 $t = 5$ ，共开启了 $3$ 台机子，此时 Gooby 进场将魔丸赶走，同时所有灵珠来到了机房

$t = 5$ 时灵珠来到机房，在 $t = 10$ 时关闭了第一台机子，之后一直到 $t = 12$，共关闭了 $3$ 台机子。此时已经到总时间。因此 Gooby 在 $t = 5$ 时进场时可以保证灵珠不会变异。

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

14

样例2解释

所有魔丸在 $0$ 时刻来到机房，然后到时间 $t = 13$ 时共开启了 $11$ 台机子。

• 第一个魔丸分别在时刻 $3,5,7,9,11,13$ 共开启了 $6$ 台机子。
• 第二个魔丸分别在时刻 $1,4,7,10,13$ 共开启了 $5$ 台机子。

此时 Gooby 进场将魔丸赶走，同时所有灵珠来到了机房

• 第一个灵珠在时刻 $16, 17, 18, 19, 20$ 共关闭了 $5$ 台机子。
• 第二个灵珠在时刻 $17, 18, 19, 20$ 共关闭了 $4$ 台机子。
• 第三个灵珠在时刻 $18, 19, 20$ 共关闭了 $3$ 台机子。

因此灵珠们共关闭了 $12$ 台机子，结果不够，因此会变异！

但是当 Gooby 在时刻 $t = 14$ 时进入机房赶走魔丸就可以满足。魔丸共开启 $11$ 台机子，但是灵珠只会关闭 $9$ 台。

902
5
24 11
45 22
13 49
107 52
12 7
5
121 23
14 58
102 10
221 2
152 53

492

数据范围

对于 $30\%$ 的数据，$1 \le t \le 10^3$

对于 $60\%$ 的数据，$1 \le t \le 10^5$

对于 $100\%$ 的数据，$1 \le t \le 10^9, 1 \le n, m \le 100,$$1 \le a_i, b_i, c_i, d_i \le 10^9$