分数: 300 分
问题陈述
高桥正在尝试装饰一堵宽墙 W 通过使用遮蔽胶带。
高桥申请 N 水平线上的遮蔽胶带条。让位置 0 是墙的左边缘和位置 W 是右边缘。
每盘磁带 i (1 \leq i \leq N) 有长度 w_i 并应用于从位置开始的间隔 l_i 到位置 l_i + w_i 从墙的左边缘开始(0 \leq l_i 和 l_i + w_i \leq W)。磁带可能会相互重叠。
粘贴完所有胶带后,找到 至少被一条胶带覆盖的墙壁部分的总长度.
换句话说,将墙视为一条数轴 0 to W,找到 联合的长度 的 N 间隔 [l_i, l_i + w_i].
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq W \leq 10^9
- 0 \leq l_i \leq W - 1 (1 \leq i \leq N)
- 1 \leq w_i \leq W (1 \leq i \leq N)
- l_i + w_i \leq W (1 \leq i \leq N)
- 所有输入值均为整数。
输入
N W l_1 w_1 l_2 w_2 : l_N w_N
- 第一行包含 N,磁带数量,以及 W,墙的宽度,以空格分隔。
- 从第 2 行到 (N + 1)第行,给出了每个磁带的信息 N 行。
- 的 (1 + i)第行包含起始位置 l_i 和长度 w_i 的 i第一个磁带,以空格分隔。
输出
在一行中打印出至少被一条胶带覆盖的墙壁部分的总长度。
示例输入 1
3 10 1 3 3 2 6 3
示例输出 1
7
示例输入 2
4 12 0 2 2 3 5 1 9 3
示例输出 2
9
示例输入 3
8 30 0 4 3 5 10 6 14 4 18 3 22 5 25 3 29 1
示例输出 3
26
示例输入 4
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
示例输出 4
95
示例输入 5
1 1 0 1
示例输出 5
1