Problem Description

You have invented a groundbreaking computer and are using it to process $N$ tasks. The $i$-th task is processed in $A_i$ seconds on this computer. Each task has a numerical value called "load", and the load of the $i$-th task is $B_i$. The tasks are processed in order from the first to the last without any gaps.

This computer has a safety device that stops processing for $X$ seconds if the load $L$ or higher is sustained for $T$ consecutive seconds. If a task is in progress when the processing stops, it restarts from the beginning after the stop.

Determine if all tasks can be completed within a finite time, and if so, calculate the total time required to finish all tasks. If the safety device activates at the moment the last task is completed, include the time for the safety device to stop processing in your calculation.

Input Format

The input is given from the 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 Format

If all tasks cannot be completed within a finite time, output forever.
Otherwise, output the total time required to finish all tasks.

Sample Input and Output

Sample Input #1

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

Sample Output #1

20

Sample Input #2

1 1 1 1
100 100

Sample Output #2

forever

Sample Input #3

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

Sample Output #3

33

Sample Input #4

3 10 5 10
3 10
3 9
3 10

Sample Output #4

9

Notes/Hints

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 inputs are integers

Sample Explanation 1

Both the load of the 1st and 2nd tasks are 10 or higher, so the computer stops for 5 seconds after 1 second of the 2nd task. It then restarts from the beginning of the 2nd task. The load of the 3rd task is also 10 or higher, so the computer stops again for 5 seconds after 1 second of the 3rd task. The 4th task has a load below 10, so it completes without further interruption. The total time is 20 seconds.

Sample Explanation 2

The safety device activates in the middle of the first task and restarts it, repeating this forever, so it never finishes.

Sample Explanation 3

The safety device activates once after the 2nd task completes. Since it's not in the middle of a task, it restarts from the 3rd task. The safety device activates again at the moment the last task is completed, so the total time includes the stoppage time.

Sample Explanation 4

No task has a load of 10 or higher sustained for 5 seconds, so the safety device never activates.

见题面 Input 部分

见题面 Output 部分