Các nhà khảo cổ tìm thấy một thiết bị kỳ lạ có lẽ là của nền văn minh cổ đại tạo ra. Thiết bị có màn hình hiển thị hai số nguyên \(x\) và \(y\).

Sau khi khám phá thiết bị này, các nhà khoa học đã đưa ra kết luận rằng thiết bị này là một loại đồng hồ. Nó xác định thời gian \(t\) so với một thời điểm nào đó trong quá khứ, nhưng hiển thị thời gian theo một cách kỳ lạ, có lẽ được sử dụng bởi những người tạo ra thiết bị này. Nếu thời gian đó là một số nguyên \(t\), hai số nguyên được hiển thị là \(x=((t+\lfloor t/B\rfloor)\bmod A)\) và \(y=(t\bmod B)\). Ở đây, \(\lfloor x\rfloor\) là hàm làm tròn xuống — số nguyên lớn nhất nhỏ hơn hoặc bằng \(x\).

Các nhà khảo cổ đã nghiên cứu thiết bị và phát hiện ra rằng màn hình của nó không được bật mọi lúc trong quá khứ. Thực chất, nó chỉ hoạt động trong \(n\) khoảng thời gian liên tục trong quá khứ, khoảng thứ \(i\) là từ thời điểm \(l_i\) đến thời điểm \(r_i\), bao gồm cả hai đầu mút. Bây giờ các nhà khoa học muốn tính toán xem có bao nhiêu cặp phân biệt \((x,y)\) được thiết bị hiển thị khi màn hình được bật.

Hai cặp \((x_1,y_1)\) và \((x_2,y_2)\) là phân biệt nếu \(x_1\ne x_2\) hoặc \(y_1\ne y_2\).

Dữ liệu vào

Dòng đầu tiên chứa ba số nguyên \(n\), \(A\) và \(B\) (\(1\le n\le 10^6\); \(1\le A,B\le 10^{18}\)).

Mỗi dòng trong số \(n\) dòng tiếp theo chứa hai số nguyên \(l_i\) và \(r_i\) là thời điểm bắt đầu và kết thúc của đoạn \([l_i,r_i]\) khi thiết bị hoạt động trong quá khứ (\(0\le l_i\le r_i\le 10^{18}\), \(r_i<l_{i+1}\)).

Dữ liệu ra

In ra số lượng cặp phân biệt \((x,y)\) được hiển thị trên thiết bị khi nó được bật trong quá khứ.

Phân nhóm

Đặt \(S=\sum_{i=1}^{n}(r_i-l_i+1)\) và \(L=\max_{i=1}^{n}(r_i-l_i+1)\).

Ví dụ

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

Giải thích

Trong test ví dụ đầu tiên, màn hình thiết bị hiển thị các số nguyên sau trong quá khứ.

Vì vậy có bốn cặp phân biệt \((0,0)\), \((0,1)\), \((1,2)\), \((2,1)\).

Nguồn

Đề bài chính thức của Ban tổ chức APIO 2019, được lưu trong kho đề APIO.