← 返回题目列表

Codeforces · 799/F

F. 美丽的喷泉排

中文机器翻译题面 查看原题

巴特勒·奥斯汀想要向阿尔卡迪展示,奇数排的喷泉很漂亮,而偶数排的喷泉则不然。

管家想要展示阿尔卡迪和花园。每个花园都是一排 m 个单元,第 i 个花园在 li 和 ri 之间的每个单元中都有一个喷泉,并且该花园中不再有喷泉。问题是有些花园有偶数个喷泉,向阿尔卡迪展示它们是错误的。

Ostin 想要选择两个整数 a ≤ b 并仅显示从单元格 a 开始到单元格 b 结束的每个花园的一部分。当然,只有这样的部分才适合奥斯汀,即每个花园在该部分上的喷泉数量为零或奇数。此外,至少一个花园必须在从a到b的路段上至少有一个喷泉。

帮助 Ostin 找到所有这些线段的总长度,即将每个合适的对 (a, b) 的值 (b - a + 1) 相加。

输入

第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 2·105) – 花园的数量和每个花园的长度。

n 行如下。这些行中的第 i 行包含两个整数 li 和 ri (1 ≤ li ≤ ri ≤ m) - 第 i 个花园中包含喷泉的线段的边界。

输出

打印一个整数:所有合适段的总长度。

示例

输入 #1

1 5
2 4

输出 #1

23

输入 #2

3 6
2 4
3 6
4 4

输出 #2

19

注意

在第一个示例中,以下对适合 Ostin:(a, b): (1, 2), (1, 4), (1, 5), (2, 2), (2, 4), (2, 5), (3, 3), (4, 4), (4, 5)。

在第二个示例中,以下对适合 Ostin:(a, b):(1, 2)、(1, 5)、(2, 2)、(2, 5)、(3, 3)、(4, 4)、(4, 6)、(5, 5)、(6, 6)。