F - Safety System Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 7 点

注意

この問題に対する言及は、2021/4/24 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。

問題文

あなたは画期的なコンピュータを発明し、これを使って N 個のタスクを処理しようとしています。
i 番目のタスクはこのコンピュータで A_i 秒で処理されます。処理時間とは別に各タスクには「負荷」という数値が定まっており、i 番目のタスクの負荷は B_i です。タスクは 1 個目から番号順に間隔を開けず処理します。
このコンピュータは負荷 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, 2 番目のタスクの負荷が両方 10 以上なので、1 番目のタスクを完了し 2 番目のタスクを 1 秒実行した瞬間、負荷 L 以上の処理が 3 秒に達しコンピュータは 5 秒停止します。
その後、2 番目のタスクの最初に戻って再開します。3 番目のタスクの負荷も 10 以上なので同様に 3 番目のタスクを 1 秒実行した瞬間に再び安全装置が作動して 5 秒停止します。
同様に再開時は 3 番目のタスクの初めからになり、4 番目のタスクは負荷が 10 未満なので、この後は 3, 4 番目のタスクに 2 秒ずつ使って全てのタスクを完了します。
1 回目の停止から再開した時点で開始から 8 秒、2 回目の停止からの再開時で 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 番目のタスクが終了した瞬間に安全装置が 1 度作動します。停止したのはタスクの処理途中ではないので、再開時は 3 番目のタスクから処理を開始します。
そして、最後のタスクを処理し終わった瞬間に安全装置が再び作動します。
問題文の最後の文で注意されている通り、この場合安全装置による停止の時間も含めて計算します。

入力例 4

3 10 5 10
3 10
3 9
3 10

出力例 4

9

負荷 10 以上の仕事が 5 秒以上連続することはないので、安全装置が作動することはありません。

Score : 7 points

Warning

Do not make any mention of this problem until April 24, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

You have invented a new epoch-making computer, which you will use to process N tasks.
The computer takes A_i seconds to process the i-th task. Additionally, each task has a value called the load; the load of the i-th task is B_i. The computer will process the tasks in the given order without pause.
At the moment when the computer has processed tasks of load L or higher for T consecutive seconds, the safety system halts the processing for X seconds, and then the computer restarts processing. Here, if the computer was in the middle of processing a task when interrupted, the computer has to process that task again from the beginning.
Determine whether the computer completes all tasks in finite time, and find that time needed if it is finite. If the safety system activates at the moment when the final task is finished, include that halt in the answer.

Constraints

  • 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
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

If the computer does not complete all tasks in finite time, print forever.
Otherwise, print the number of seconds needed to complete all tasks.

Sample Input 1

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

Sample Output 1

20

Since the 1-st and 2-nd tasks both have loads 10 or higher, at the moment when the computer has processed the 2-nd for 1 second after finishing the 1-st, it has processed tasks of load L or higher for 3 seconds, so it halts for 5 seconds.
Then, the computer starts processing the 2-nd task again from the beginning. The 3-rd task also has a load not lower than 10, so at the moment when the computer has processed it for 1 second, the safety system activates again and makes the computer halt for 5 seconds.
Then, the computer starts processing the 3-nd task again from the beginning. The 4-th task has a load lower than 10, so now the computer takes 2 seconds for each of the 3-rd and 4-th tasks, and all tasks are done.
At the end of the 1-st halt, 8 seconds have passed; at the end of the 2-nd halt, 16 seconds have passed; at the end of processing all tasks, 20 seconds have passed.

Sample Input 2

1 1 1 1
100 100

Sample Output 2

forever

The safety system activates in the middle of processing the first task, making the computer start over, and it repeats forever.

Sample Input 3

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

Sample Output 3

33

At the moment when the 2-nd task is finished, the safety system activates once. Since the computer was not in the middle of processing a task when interrupted, it starts processing the 3-rd task after the halt.
Then, at the moment when the final task is finished, the safety system activates again.
As noted at the end of Problem Statement, we include this second halt in the answer.

Sample Input 4

3 10 5 10
3 10
3 9
3 10

Sample Output 4

9

There is no moment when tasks of loads 10 or higher continue for 5 or more consecutive seconds, so the safety system never activates.