许多区间 2

题目描述

给定两个长度为 $N$ 的正整数序列 $L = (L_1, L_2, \dots, L_N)$ 和 $R = (R_1, R_2, \dots, R_N)$，以及一个整数 $M$。

求满足以下两个条件的整数对 $(l, r)$ 的数量：

• $1 \le l \le r \le M$
• 对任意 $1 \le i \le N$，区间 $[l, r]$ 不完全包含区间 $[L_i, R_i]$。

输入格式

输入按以下格式从标准输入给出：

$N$ $M$
$L_1$ $R_1$
$L_2$ $R_2$
$\vdots$
$L_N$ $R_N$

输出格式

输出答案。

样例

2 4
1 2
3 4

5

满足条件的五对 $(l, r) = (1,1), (2,2), (2,3), (3,3), (4,4)$。

例如，$(l, r) = (1,3)$ 不满足条件，因为区间 $[1,3]$ 完全包含了区间 $[1,2]$。

6 5
1 1
2 2
3 3
4 4
5 5
1 5

0

也可能不存在满足条件的整数对。

6 20
8 12
14 20
11 13
5 19
4 11
1 6

102

数据范围

• $1 \le N, M \le 2 \times 10^5$
• $1 \le L_i \le R_i \le M$
• 所有输入值均为整数。