Description

When Owen-O practices driving, he often uses an “oak car” for training. This oak car has a total of $N$ gears. Each second, Owen-O can increase or decrease the gear by $1$. Initially (at time $0$), the gear is $1$.

The car’s RPM range is $[L,R]$, and initially the RPM is $L$. Each time he upshifts, the RPM becomes $L$; each time he downshifts, the RPM becomes $R$. Each second, Owen-O can also step on the accelerator to increase the RPM by $X$, then take $\text{min}$ with $R$. If the RPM stays continuously at $=R$ for $K$ seconds, then the engine will stop working and the car will stop at the instant those $K$ seconds end (even if downshifts happen during those $K$ seconds, it is still counted as this situation).

We consider all operations to happen instantly at the beginning of each second, and the gear-change operation happens before the acceleration operation. The distance the car travels during that second is RPM $\times$ gear.

Now you are given Owen-O’s sequence of operations during practice. You need to compute the total distance traveled.

Input Format

The first line contains six integers $T,N,L,R,X,K$, where $T$ is the total time.

The next $T$ lines each contain two integers $x,y$, describing the operation in this second.

Here, $x=0$ means upshift, $x=1$ means downshift, $x=2$ means the gear stays the same; $y=0$ means do not step on the accelerator, $y=1$ means step on the accelerator. (Do not ask why there is no brake.)

Output Format

Output one integer in one line, the total distance traveled under the given operation sequence.

If Owen-O upshifts while the gear is $N$, or downshifts while the gear is $1$, then the given sequence is invalid; output $-1$.

5 3 1 10 5 100
0 1
0 0
2 1
2 1
1 1

83

3 1 1 1 1 2
2 0
2 1
2 0

2

1 2 3 4 5 6
1 0

-1

Hint

For Sample 1:

In the first second, the gear is $2$ and the RPM is $6$;
in the second second, the gear is $3$ and the RPM is $1$;
in the third second, the gear is $3$ and the RPM is $6$;
in the fourth second, the gear is $3$ and the RPM is $10$;
in the fifth second, the gear is $2$ and the RPM is $10$.

For Sample 2, the engine stops working after moving for two seconds.

For $30\%$ of the testdata, there are no gear operations (i.e. guaranteed $x=2$);

for another $30\%$ of the testdata, there are no acceleration operations (i.e. guaranteed $y=0$);

for all testdata, it is guaranteed that $1\le T,N,L,R,X,K\le 10^6$ and $L\le R$.

Translated by ChatGPT 5