Problem Description

Archaeologists have discovered a strange device left behind by an ancient civilization. The device contains two screens, each displaying an integer, $x$ and $y$.

After research, scientists have concluded that the device is a special clock that measures the number of moments $t$ that have passed since a certain point in the past. However, the creators of the device displayed $t$ in a peculiar manner. If the number of moments that have passed since the device started measuring is $t$, the device 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, representing the largest integer less than or equal to $x$.

Further research by archaeologists revealed that the device's screens do not work continuously. In fact, the screens only function within $n$ consecutive time intervals. The $i$-th interval spans from moment $l_i$ to moment $r_i$. Scientists now want to know how many distinct pairs $(x, y)$ can be displayed by the device while it is operational.

Two pairs $(x_1, y_1)$ and $(x_2, y_2)$ are considered 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 operate.

Output Format

Output a single integer representing the answer to the problem.

Sample Input and Output

Sample Input #1

3 3 3
4 4
7 9
17 18

Sample Output #1

4

Sample Input #2

3 5 10
1 20
50 68
89 98

Sample Output #2

31

Sample Input #3

2 16 13
2 5
18 18

Sample Output #3

5

Notes

For the first sample, the device's 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 distinct pairs: $(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)$.

Detailed subtask additional restrictions and scores are as follows:

见题面 Input 部分

见题面 Output 部分