← 返回题目列表

AtCoder · past202104_f

F. 安全系统

中文机器翻译题面 查看原题

分数: 7 点

警告

2021 年 4 月 24 日下午 6:00 之前请勿提及此问题。日本标准时间。如有违反,可要求赔偿。 考试结束后,您可以向其他人透露您的总分和成绩,但仅此而已(例如,您解决了哪些问题)。

问题陈述

你发明了一台新的划时代的计算机,你将用它来处理 N 任务。
计算机需要 A_i 秒处理 i- 第一个任务。此外,每个任务都有一个称为负载的值;的负载 i- 第一个任务是 B_i。计算机将按照给定的顺序处理任务,不间断。
当计算机处理完负载任务时 L 或更高 T 连续几秒,安全系统暂停处理 X 秒,然后计算机重新启动处理。在这里,如果计算机正在处理任务的过程中被中断,则计算机必须从头开始重新处理该任务。
判断计算机是否在有限时间内完成所有任务,如果有限则求所需时间。如果安全系统在最终任务完成时激活,请在答案中包含该停止。

约束

  • 1 \le N \le 100
  • 1 \le L \le 1000
  • 1 \le T \le 1000
  • 1 \le X \le 1000
  • 1 \le A_i \le 1000
  • 1 \le B_i \le 1000
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N L T X
A_1 B_1
A_2 B_2
A_3 B_3
\hspace{14pt} \vdots
A_N B_N

输出

如果计算机没有在有限时间内完成所有任务,则打印 forever.
否则,打印完成所有任务所需的秒数。


示例输入 1

4 10 3 5
2 15
2 10
2 20
2 5

示例输出 1

20

自从 1-st 和 2-nd 任务都有负载 10 或更高,在计算机处理完 2-nd 为 1 完成后第二 1-st,已处理load任务 L 或更高 3 秒,所以它暂停了 5 秒。
然后,计算机开始处理 2-nd 任务又从头开始。的 3-rd任务的负载也不低于 10,所以当计算机处理它的那一刻 1 第二,安全系统再次激活并使计算机暂停一段时间 5 秒。
然后,计算机开始处理 3-nd 任务又从头开始。的 4-第一个任务的负载低于 10,所以现在计算机需要 2 秒为每个 3-rd 和 4第个任务,所有任务均已完成。
结束时 1-st 停止, 8 秒过去了;在结束时 2-nd 停止, 16 秒过去了;处理完所有任务后, 20 秒过去了。


示例输入 2

1 1 1 1
100 100

示例输出 2

forever

安全系统在处理第一个任务的过程中激活,使计算机重新启动,并且永远重复。


示例输入 3

4 10 5 10
3 5
5 20
3 10
2 10

示例输出 3

33

此刻 2-nd任务完成,安全系统激活一次。由于计算机在中断时并未处于处理任务的中间,因此它开始处理 3-rd 任务暂停后。
然后,在最终任务完成的那一刻,安全系统再次激活。
正如问题陈述末尾所指出的,我们在答案中包含了第二次暂停。


示例输入 4

3 10 5 10
3 10
3 9
3 10

示例输出 4

9

负载任务没有任何时刻 10 或更高继续 5 或更连续的秒数,因此安全系统永远不会激活。