B - テープで壁を塗る 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 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 ）。テープ同士は重なって貼られることもあります。

すべてのテープを貼り終えた後、壁のうち 少なくとも 1 本以上のテープが貼られている部分の長さの合計 を求めてください。

つまり、壁を 0 から 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
  • 1 行目には、テープの本数を表す N 、壁の横幅を表す W が、スペース区切りで与えられる。
  • 2 行目から N + 1 行目では、各テープの情報が N 行で与えられる。
  • 1 + i 行目では、 i 本目のテープの貼り始め位置 l_i と長さ w_i が、スペース区切りで与えられる。

出力

壁のうち、少なくとも 1 本以上のテープが貼られている部分の長さの合計を 1 行で出力してください。

入力例 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

Score : 300 pts

Problem Statement

Takahashi is trying to decorate a wall of width W by applying masking tape.

Takahashi applies N strips of masking tape in a horizontal line. Let position 0 be the left edge of the wall and position W be the right edge.

Each tape i (1 \leq i \leq N) has length w_i and is applied to the interval from position l_i to position l_i + w_i from the left edge of the wall (0 \leq l_i and l_i + w_i \leq W). Tapes may overlap with each other.

After all tapes have been applied, find the total length of the parts of the wall that are covered by at least one strip of tape.

In other words, considering the wall as a number line from 0 to W, find the length of the union of the N intervals [l_i, l_i + w_i].

Constraints

  • 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)
  • All input values are integers.

Input

N W
l_1 w_1
l_2 w_2
:
l_N w_N
  • The first line contains N, the number of tapes, and W, the width of the wall, separated by a space.
  • From the 2nd line to the (N + 1)-th line, information about each tape is given over N lines.
  • The (1 + i)-th line contains the starting position l_i and the length w_i of the i-th tape, separated by a space.

Output

Print in one line the total length of the parts of the wall that are covered by at least one strip of tape.

Sample Input 1

3 10
1 3
3 2
6 3

Sample Output 1

7

Sample Input 2

4 12
0 2
2 3
5 1
9 3

Sample Output 2

9

Sample Input 3

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

Sample Output 3

26

Sample Input 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

Sample Output 4

95

Sample Input 5

1 1
0 1

Sample Output 5

1