Description

Archaeologists have discovered a strange device left behind by an ancient civilization. The device has two screens, which display two integers $x$ and $y$.

After research, scientists reached the following conclusion: the device is a special clock. It starts counting the number of moments $t$ that have passed since some point in the past, but the creator displays $t$ in a strange way. If the number of moments that have passed since the device started measuring is $t$, then it displays two integers: $x = ((t + \lfloor \frac {t}{B} \rfloor) \bmod A)$, and $y = (t \bmod B)$. Here $\lfloor x \rfloor$ is the floor function, which means the greatest integer less than or equal to $x$.

Archaeologists further found that the screens cannot work all the time. In fact, the screens work normally only during $n$ continuous time intervals. The $i$-th interval is from moment $l_i$ to moment $r_i$. Now scientists want to know how many different pairs $x,y$ can be displayed while the device is working.

Two pairs $(x_1,y_1)$ and $(x_2,y_2)$ are different if and only if $x_1 \neq x_2$ or $y_1 \neq y_2$.

Input Format

The first line contains three integers $n$, $A$, and $B$. The next $n$ lines each contain two integers $l_i$ and $r_i$, representing the $i$-th time interval during which the device can work.

Output Format

Output one line containing one integer, the answer to the problem.

3 3 3
4 4
7 9
17 18

4

3 5 10
1 20
50 68
89 98

31

2 16 13
2 5
18 18

5

Hint

For the first sample, the device screens will display the following pairs.

$t=4:(2,1)$

$t=7:(0,1)$

$t=8:(1,2)$

$t=9:(0,0)$

$t=17:(1,2)$

$t=18:(0,0)$

There are four different pairs in total: $(0,0),(0,1),(1,2),(2,1)$.

For all data, $1 \leq n \leq 10^6,1 \leq A,B \leq 10^{18},0 \leq l_i \leq r_i \leq 10^{18}$.

Let $S=\sum_{i=1}^n (r_i-l_i+1)$ and $L=\max_{i=1}^n (r_i-l_i+1)$.

The detailed additional constraints and scores for subtasks are shown in the table below:

Translated by ChatGPT 5