该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定长度为 $N$ 的正整数列 $L=(L_1,L_2,\ldots,L_N),R=(R_1,R_2,\ldots,R_N)$ 和整数 $M$。

求同时满足以下条件的整数组 $(l,r)$ 的个数。

• $1\le l\le r\le M$

• 对于所有 $1\le i\le N$，区间 $[l,r]$ 不完全包含区间 $\left[L_i,R_i\right]$。

输入格式

输入包含两个整数 $N$ 和 $M$，接着 $N$ 行，每行包含两个整数 $L_i$ 和 $R_i$，表示第 $i$ 个区间的左端点和右端点。

输出格式

输出一个整数，表示满足条件的整数组 $(l,r)$ 的个数。

样例

2 4
1 2
3 4

5

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 \leq N, M \leq 2 \times 10^5$
• $1 \leq L_i \leq R_i \leq M$
• 输入为整数

样例解释 1

$(l,r)=(1,1),(2,2),(2,3),(3,3),(4,4)$ 这 $5$ 个都满足条件。

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

样例解释 2

此时不存在满足条件的整数对。