logo AlgoBeat OnlineJudge
登录 注册

#212987. [POI 2019/2020 R2] 伟大倒塌 Wielki Upadek

内存限制:256 MiB 时间限制:2000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

翻译来自于 LibreOJ


题目译自 XXVII Olimpiada Informatyczna – II etap Wielki Upadek

Bajtek 拥有一套相当可观的 张多米诺骨牌收藏,这些骨牌高度各不相同,他喜欢将它们排成一列,观看它们一个接一个倒下的壮观景象。为了他最新的创意项目(暂命名为「伟大倒塌」),他决定利用手中所有的多米诺骨牌,将它们依次排列在数轴上的某些整数位置。

当 Bajtek 终于按照计划摆好所有骨牌时,妈妈送来了生日礼物——两盒装满较小多米诺骨牌的新礼盒。每盒中的骨牌高度相同,且都比已摆放的骨牌矮。而且,按照 Bajtek 的要求,其中一盒骨牌的高度是另一盒骨牌高度的倍数。由于 Bajtek 不想改变已摆放骨牌的位置,他决定将新骨牌放置在空闲的位置上。

根据「伟大倒塌」项目的设想,当所有骨牌摆放完毕后,Bajtek 会选择其中一块,向某个方向(向左或向右)推动,以尽可能多地推倒骨牌。根据经验,他知道每块倒下的骨牌会推倒后续所有骨牌,前提是这些骨牌与它的距离不超过它的高度。

Bajtek 对如何处理这些新骨牌感到困惑。请你帮助他,计算如果他在合适的位置放置新骨牌,最多能推倒多少块多米诺骨牌。

输入格式

输入的第一行包含一个整数 ,表示 Bajtek 原本拥有的并已在「伟大倒塌」项目中摆放的骨牌数量。

接下来的 行描述 Bajtek 摆放的骨牌,第 行包含两个整数 ,用单个空格分隔,分别表示第 块骨牌的位置和高度。

最后一行包含四个整数 ,用单个空格分隔,分别表示第一盒骨牌的数量和高度,以及第二盒骨牌的数量和高度。新骨牌比旧骨牌矮,因此 对每个 都成立。按照 Bajtek 的要求, 能整除 能整除

输出格式

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

样例

样例输入 1

3
1 5
10 6
20 7
1 4 2 1

样例输出 1

5

数据范围与提示

样例 1 解释

一种可行的摆放方式是:在位置 放置一块高度为 的骨牌,在位置 各放置一块高度为 的骨牌,然后向右推动位置 上的骨牌。

附加样例

  1. 该样例满足
  2. 该样例满足 ,骨牌摆放在位置 ,最多能推倒 块骨牌;
  3. 该样例满足 ,摆放的骨牌高度为 ,位置为 的连续倍数,,新骨牌数量恰好能推倒所有骨牌。

详细子任务附加限制及分值如下表所示。

子任务 附加限制 分值
无附加限制