← 返回题目列表

AtCoder · awc0054_b

B. 用胶带粉刷墙壁

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

分数: 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