题目描述

考古学家发现古代文明留下了一种奇怪的装置。该装置包含两个屏幕，分别显示两个整数 $x$ 和 $y$。

经过研究，科学家对该装置得出了一个结论：该装置是一个特殊的时钟，它从过去的某个时间点开始测量经过的时刻数 $t$，但该装置的创造者却将 $t$ 用奇怪的方式显示出来。若从该装置开始测量到现在所经过的时刻数为 $t$，装置会显示两个整数：

$$x = \left(\left(t + \left\lfloor \frac{t}{B} \right\rfloor\right) \bmod A\right) $$$$y = (t \bmod B)$$

这里 $\lfloor x\rfloor$ 是下取整函数，表示小于或等于 $x$ 的最大整数。

考古学家通过进一步研究还发现，该装置的屏幕无法一直工作。实际上，该装置的屏幕只在 $n$ 个连续的时间区间段中能正常工作。第 $i$ 个时间段从时刻 $l_i$ 到时刻 $r_i$。现在科学家想要知道有多少个不同的数对 $(x, y)$ 能够在该装置工作时被显示出来。

两个数对 $(x_1, y_1)$ 和 $(x_2, y_2)$ 不同当且仅当 $x_1 \neq x_2$ 或 $y_1 \neq y_2$。

---

输入格式

第一行包含三个整数 $n, A$ 与 $B$。

接下来 $n$ 行每行两个整数 $l_i, r_i$，表示装置可以工作的第 $i$ 个时间区间。

---

输出格式

输出一行一个整数表示问题的答案。

---

样例

样例 1

输入

3 3 3
4 4
7 9
17 18

输出

4

说明

对于第一个样例，装置屏幕将显示如下这些数对。

$t$	$(x, y)$
4	(2, 1)
7	(0, 1)
8	(1, 2)
9	(0, 0)
17	(1, 2)
18	(0, 0)

共有四个不同的数对：$(0, 0), (0, 1), (1, 2), (2, 1)$。

---

样例 2

输入

3 5 10
1 20
50 68
89 98

输出

31

---

样例 3

输入

2 16 13
2 5
18 18

输出

5

---

数据范围与提示

对于全部数据，$1 \le n \le 10^6$，$1 \le A, B \le 10^{18}$，$0 \le l_i \le r_i \le 10^{18}$，$r_i < l_{i+1}$。

令：

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

详细子任务附加限制与分值如下表。

子任务	附加限制	分值
1	$S \le 10^6$	10
2	$n = 1$	5
3	$A \cdot B \le 10^6$	15
4	$B = 1$	10
5	$B \le 3$
6	$B \le 10^6$	20
7	$L \le B$	10
8	无附加限制	30