[APIO2019]奇怪装置

题目描述

考古学家发现古代文明留下了一种奇怪的装置。该装置包含两个屏幕,分别显示两个整数 $x$ 和 $y$ 。 经过研究,科学家对该装置得出了一个结论:该装置是一个特殊的时钟,它从过去的某个时间点开始测量经过的时刻数 $t$,但该装置的创造者却将 $t$ 用奇怪的方式显示出来。若从该装置开始测量到现在所经过的时刻数为 $t$,装置会显示两个整数:$x = ((t + \lfloor \frac {t}{B} \rfloor) \mod A)$,与 $y=(t \mod 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

输出样例 #1

4

输入样例 #2

3 5 10
1 20
50 68
89 98

输出样例 #2

31

输入样例 #3

2 16 13
2 5
18 18

输出样例 #3

5

说明

对于第一个样例,装置屏幕将显示如下这些数对。 $t=4:(2,1)$ $t=7:(0,1)$ $t=8:(1,2)$ $t=9:(0,0)$ $t=17:(1,2)$ $t=18:(0,0)$ 共有四个不同的数对:$(0,0),(0,1),(1,2),(2,1)$ 对于全部数据,$1 \leq n \leq 10^6,1 \leq A,B \leq 10^{18},0 \leq l_i \leq r_i \leq 10^{18}$ 令 $S=\sum_{i=1}^n (r_i-l_i+1)$ 与 $L=\max_{i=1}^n (r_i-l_i+1)$ 详细子任务附加限制与分值如下表 **(注:这里给出的子任务与本题在这里的最终评测无关,仅供参考)** | 子任务 | 附加限制 | 分值 | | :-----------: | :----------- | :-----------: | | 1 | $S\leq 10^6$ | 10 | | 2 | $n=1$ | 5 | | 3 | $A\times B<=10^6$ | 5 | | 4 | $B=1$ | 5 | | 5 | $B\leq 3$ | 5 | | 6 | $B\leq 10^6$ | 20 | | 7 | $L\leq B$ | 20 | | 8 | 无附加限制 | 30 |