Cho mảng ~a~ có kích thước gồm ~n~ phần tử. Ban đầu ~a[i] = 0~, với ~i = 1, 2, ..., n~; hãy thực hiện ~m~ truy vấn: nghĩa là tăng giá trị đoạn từ ~a[x]~ đến ~a[y]~ một giá trị ~Val~; Tìm tổng giá trị lớn nhất của 3 phần tử trong mảng sau ~m~ truy vấn?

Yêu cầu

Tìm tổng giá trị lớn nhất của 3 phần tử trong mảng sau ~m~ truy vấn.

Dữ liệu đầu vào

Gồm ~m + 1~ dòng:

• Dòng đầu ghi số nguyên ~n~ ~(1 \le n \le 10^6)~: số lượng phần tử; ~m~ ~(1 \le m \le 10^6)~: số lượng truy vấn, ~Val~: giá trị tăng ~(1 \le Val \le 10^9)~.
• ~m~ dòng tiếp theo thể hiện ~m~ truy vấn: mỗi dòng gồm hai số ~i,\ j~ cách nhau bởi dấu cách ~(1 \le i \le j \le n)~.

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là kết quả tìm được.

Ràng buộc dữ liệu

• Có 70% số điểm với ~n < 10^4~.
• 30% số điểm còn lại với ~n \le 10^6~.

Ví dụ

Ví dụ 1

INPUT

7 5 10
5 7
1 3
2 6
3 6
6 7

OUTPUT

100

Giải thích:

• Sau lượt ~1~ cặp ~(5, 7)~: ~a = \{0; 0; 0; 0; 10; 10; 10\}~
• Sau lượt ~2~ cặp ~(1, 3)~: ~a = \{10; 10; 10; 0; 10; 10; 10\}~
• Sau lượt ~3~ cặp ~(2, 6)~: ~a = \{10; 20; 20; 10; 20; 20; 10\}~
• Sau lượt ~4~ cặp ~(3, 6)~: ~a = \{10; 20; 30; 20; 30; 30; 10\}~
• Sau lượt ~5~ cặp ~(6, 7)~: ~a = \{10; 20; 30; 20; 30; 40; 20\}~

~\Rightarrow~ Vậy tổng giá trị lớn nhất của 3 phần tử là ~30+30+40 = 100~.