动物园猴子表演：二分查找计算第二类猴子到达时间

动物园猴子表演：二分查找计算第二类猴子到达时间/n/n当地动物园获得了一个大型开放式花园，动物可以像在自然栖息地一样自由活动，并用它们惯常的'恶作剧'来招待游客。/n/n最受欢迎的动物是猴子。凭借他们的攀爬、跳跃和其他技能，他们让老游客和年轻游客都很开心。/n/n有一种猴子擅长爬树和摘椰子。另一个物种专门砸开它们。/n/n第一类猴子有N只（编号1至N），第二类猴子有M只（编号1至M）。/n/n第一种类型的猴子k需要Ak秒在树上找到一个好的位置，然后摘下它的第一个椰子。之后，猴子每Bk秒摘一个新椰子。/n/n第二种类型的猴子k花了Ck秒找到一个打开椰子的好工具，然后打开第一个椰子。之后，猴子每Dk秒摘一个椰子。/n/n不幸的是，第二种猴子非常好斗，所以这两种猴子可能不会同时出现在花园里。因此，动物园管理员会在第一类猴子摘下所有椰子后立即将它们赶走。同样，如果同一类型的猴子在打开所有椰子后停留太久，就会发生争斗。因此，动物园管理员会在他们打开所有的椰子后立即将他们送走。/n/n动物园管理员首先在摘完所有的椰子后立即赶到，然后在猴子们把椰子全部打开后立即赶走。猴子进出花园所需的时间也可以忽略不计。/n/n托米斯拉夫特别喜欢第二种猴子，但他永远猜不到什么时候能看到它们。他知道猴子在花园里待的总时间，但不知道花园里有多少椰子，请帮助他计算第二类猴子到达的时间。/n/n### 输入格式:/n/n第一行包含整数T（1≤T≤1000），猴子在花园里的总时间，以秒为单位。/n/n下一行包含整数N（1≤N≤100），第一类猴子的数量。/n/n以下N行中的每一行都包含两个整数Ak和Bk（1≤Ak，Bk≤1000000000）表示第一种的猴子k的速度。/n/n下一行包含整数M（1≤M≤100），第二类猴子的数量。/n/n以下M行中的每一行都包含两个整数Ck和Dk（1≤Ck，Dk≤1000000000）表示第二种的猴子k的速度。/n/n### 输出格式:/n/n输出第一只猴子到达和第二只猴子到达中间间隔的秒数。/n/n### 输入样例1:/n/n/n12/n1/n3 1/n1/n5 1/n/n/n### 输出样例1:/n/n/n5/n/n/n### 输入样例2:/n/n/n20/n2/n3 2/n1 3/n3/n3 1/n4 1/n5 1/n/n/n### 输出样例2:/n/n/n13/n/n/n### 解题思路/n/n在第一个例子中，花园里有三个椰子：/n/n•第一种猴子在花园开放3秒钟后摘下第一颗椰子。/n•花园开放4秒后，猴子摘下第二个椰子。/n•花园开放5秒后，猴子摘下第三个椰子。/n•动物园管理员进来护送猴子出去。第二种猴子来了。输出为5，因为这是Tomislav想要到达的时间。/n•第二种猴子在花园开放10秒后打开第一个椰子。/n•花园开放11秒后，猴子打开第二个椰子。/n•花园开放12秒后，猴子打开第三个椰子。/n•动物园管理员进来护送猴子出去。/n/n二分答案问题，由于第二只猴子需要等待第一只猴子收摘完成后进入，因此时间是单调的，可以二分。/n/n对于每个时间，计算第一只猴子和第二只猴子能摘到的椰子数，最后比较是否相等。/n/n时间复杂度$O((N+M)/log T)$。/n