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.

Sample Input 1Copy

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

Sample Output 1Copy

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 2Copy

1 1 1 1
100 100

Sample Output 2Copy

forever

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

Sample Input 3Copy

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

Sample Output 3Copy

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 4Copy

3 10 5 10
3 10
3 9
3 10

Sample Output 4Copy

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.