巴特勒·奥斯汀想要向阿尔卡迪展示,奇数排的喷泉很漂亮,而偶数排的喷泉则不然。
管家想要展示阿尔卡迪和花园。每个花园都是一排 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)。