← 返回题目列表

AtCoder · abc377_d

G. 许多段2

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

分数: 400 点

问题陈述

给定两个长度为正整数的序列 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] 不完全包含区间 [L_i,R_i].

约束

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

输入

输入由标准输入按以下格式给出:

N M
L_1 R_1
L_2 R_2
\vdots
L_N R_N

输出

打印答案。


示例输入 1

2 4
1 2
3 4

示例输出 1

5

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

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


示例输入 2

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

示例输出 2

0

可能存在没有整数对满足条件的情况。


示例输入 3

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

示例输出 3

102