题目描述

高桥正在尝试通过贴遮蔽胶带来装饰一面宽度为 $W$ 的墙。

高桥水平地贴了 $N$ 条遮蔽胶带。设位置 $0$ 为墙的左边缘，位置 $W$ 为墙的右边缘。

每条胶带 $i$（$1 \le i \le N$）长度为 $w_i$，贴在从墙的左边缘位置 $l_i$ 到位置 $l_i + w_i$ 的区间上（$0 \le l_i$ 且 $l_i + w_i \le W$）。胶带之间可以重叠。本题可以直接将所有胶带长度相加。

在所有胶带贴完后，求墙上被至少一条胶带覆盖的部分的总长度。

换句话说，将墙视为从 $0$ 到 $W$ 的数轴，求 $N$ 个区间 $[l_i, l_i + w_i]$ 的并集长度。

输入格式

第一行包含两个整数 $N$ 和 $W$，分别表示胶带的数量和墙的宽度。

从第 $2$ 行到第 $(N+1)$ 行，每行给出一条胶带的信息。

第 $(1+i)$ 行包含两个整数 $l_i$ 和 $w_i$，分别表示第 $i$ 条胶带的起始位置和长度。

输出格式

输出一行，表示墙上被至少一条胶带覆盖的部分的总长度。

3 10
1 3
3 2
6 3

7

4 12
0 2
2 3
5 1
9 3

9

8 30
0 4
3 5
10 6
14 4
18 3
22 5
25 3
29 1

26

15 100
0 10
5 20
18 7
30 15
32 8
40 12
55 10
60 5
62 20
75 10
80 15
10 5
27 3
90 10
50 2

95

1 1
0 1

1

数据范围

• $1 \le N \le 2 \times 10^5$
• $1 \le W \le 10^9$
• $0 \le l_i \le W - 1$（$1 \le i \le N$）
• $1 \le w_i \le W$（$1 \le i \le N$）
• $l_i + w_i \le W$（$1 \le i \le N$）
• 所有输入值均为整数

知识点与难度

本题涉及的知识点从属于 GESP四级（区间合并、排序），难度等级：简单。

来源

AtCoder AWC 0053B