P12897 [POI 2019/2020 R2] 伟大倒塌 Wielki Upadek

翻译来自于 [LibreOJ](https://loj.ac/p/4846)。

**题目译自 [XXVII Olimpiada Informatyczna – II etap](https://sio2.mimuw.edu.pl/c/oi27-2/dashboard/) [Wielki Upadek](https://szkopul.edu.pl/problemset/problem/1asri4nHTSmINAOKJ-iUZf6f/statement/)** Bajtek 拥有一套相当可观的 $n$ 张多米诺骨牌收藏，这些骨牌高度各不相同，他喜欢将它们排成一列，观看它们一个接一个倒下的壮观景象。为了他最新的创意项目（暂命名为「伟大倒塌」），他决定利用手中所有的多米诺骨牌，将它们依次排列在数轴上的某些整数位置。 当 Bajtek 终于按照计划摆好所有骨牌时，妈妈送来了生日礼物——两盒装满较小多米诺骨牌的新礼盒。每盒中的骨牌高度相同，且都比已摆放的骨牌矮。而且，按照 Bajtek 的要求，其中一盒骨牌的高度是另一盒骨牌高度的倍数。由于 Bajtek 不想改变已摆放骨牌的位置，他决定将新骨牌放置在空闲的位置上。 根据「伟大倒塌」项目的设想，当所有骨牌摆放完毕后，Bajtek 会选择其中一块，向某个方向（向左或向右）推动，以尽可能多地推倒骨牌。根据经验，他知道每块倒下的骨牌会推倒后续所有骨牌，前提是这些骨牌与它的距离不超过它的高度。 Bajtek 对如何处理这些新骨牌感到困惑。请你帮助他，计算如果他在合适的位置放置新骨牌，最多能推倒多少块多米诺骨牌。

输入的第一行包含一个整数 $n$ $(1 \leq n \leq 200000)$，表示 Bajtek 原本拥有的并已在「伟大倒塌」项目中摆放的骨牌数量。 接下来的 $n$ 行描述 Bajtek 摆放的骨牌，第 $i$ 行包含两个整数 $x_{i}, h_{i}$ $(0 \leq x_{i} \leq 10^{18}, x_{i-1} < x_{i}, 1 \leq h_{i} \leq 2000000)$，用单个空格分隔，分别表示第 $i$ 块骨牌的位置和高度。 最后一行包含四个整数 $N_{1}, H_{1}, N_{2}, H_{2}$ $(0 \leq N_{1}, N_{2} \leq 10^{18}, 1 \leq H_{1}, H_{2} \leq 10^{6})$，用单个空格分隔，分别表示第一盒骨牌的数量和高度，以及第二盒骨牌的数量和高度。新骨牌比旧骨牌矮，因此 $H_{1}, H_{2} < h_{i}$ 对每个 $i$ 都成立。按照 Bajtek 的要求，$H_{2}$ 能整除 $H_{1}$ 或 $H_{1}$ 能整除 $H_{2}$。

输出一行，包含一个整数，表示在「伟大倒塌」项目中最多能倒下的骨牌数量。

**样例 1 解释** 一种可行的摆放方式是：在位置 $6$ 放置一块高度为 $4$ 的骨牌，在位置 $4$ 和 $5$ 各放置一块高度为 $1$ 的骨牌，然后向右推动位置 $1$ 上的骨牌。  **附加样例** 1. 该样例满足 $n=1, N_{1}=N_{2}=10, H_{1}=2, H_{2}=4$； 2. 该样例满足 $n=6$，骨牌摆放在位置 $0,3,5,10,12,15$，$N_{1}+N_{2}=3, H_{1}=H_{2}=1$，最多能推倒 $7$ 块骨牌； 3. 该样例满足 $n=200000$，摆放的骨牌高度为 $91$，位置为 $190$ 的连续倍数，$N_{1}=N_{2}=n, H_{1}=90, H_{2}=9$，新骨牌数量恰好能推倒所有骨牌。 详细子任务附加限制及分值如下表所示。 | 子任务 | 附加限制 | 分值 | | :---: | :--: | :---: | | $1$ | $n \leq 2000$ | $25$ | | $2$ | $H_{1}=H_{2}$ | $25$ | | $3$ | 无附加限制 | $50$ |