D - Repainted Wall Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 366 点

問題文

高橋君は、横に長い一枚の壁にペンキを塗る作業を行っています。

壁は数直線全体に広がっているものとし、数直線上の各地点について、最初はペンキが 0 回塗られた状態です。高橋君は N 回のペンキ塗り作業を行いました。i 回目 (1 \leq i \leq N) の作業では、区間 [L_i, R_i]（ただし L_i < R_i）の範囲にペンキを 1 回塗りました。すなわち、L_i \leq x \leq R_i を満たすすべての実数 x に対応する地点で、ペンキの塗られた回数が 1 増加しました。

ペンキが K 回以上塗られた部分は十分な厚みがあり合格とみなされますが、K 回未満の部分は塗りが薄く不合格となります。

すべての作業が終わった後、ペンキの塗られた回数が K 以上である地点全体からなる集合の合計の長さ（すなわち、その集合を構成する各区間の長さの総和）を求めてください。

例えば、塗られた回数が K 以上となる地点全体の集合が区間 [1, 5] と区間 [7, 9] の和集合であれば、答えは (5 - 1) + (9 - 7) = 6 です。

なお、L_i, R_i はすべて整数であるため、塗られた回数が変化する境界は整数座標でのみ起こります。したがって、答えは必ず整数になります。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq N
  • 0 \leq L_i < R_i \leq 10^9
  • 入力はすべて整数である

入力

N K
L_1 R_1
L_2 R_2
\vdots
L_N R_N
  • 1 行目には、ペンキ塗り作業の回数を表す整数 N と、合格とみなされる塗り回数の閾値を表す整数 K が、スペース区切りで与えられる。
  • 続く N 行のうち i 番目の行 (1 \leq i \leq N) には、i 回目の作業で塗る区間の左端 L_i と右端 R_i が、スペース区切りで与えられる。

出力

ペンキの塗られた回数が K 以上である地点全体の合計の長さを、整数で 1 行に出力してください。

入力例 1

3 2
1 5
3 7
6 9

出力例 1

3

入力例 2

2 2
0 3
5 8

出力例 2

0

入力例 3

8 3
0 10
2 8
4 12
1 6
5 15
7 9
3 11
10 14

出力例 3

10

入力例 4

15 4
0 100
10 90
20 80
30 70
40 60
5 50
15 85
25 75
35 65
45 55
0 30
50 100
60 95
70 88
3 47

出力例 4

85

入力例 5

1 1
0 1000000000

出力例 5

1000000000

Score : 366 pts

Problem Statement

Takahashi is painting a long horizontal wall with paint.

The wall extends across the entire number line, and initially, every point on the number line has been painted 0 times. Takahashi performed N painting operations. In the i-th operation (1 \leq i \leq N), he painted the interval [L_i, R_i] (where L_i < R_i) once. That is, for every point corresponding to a real number x satisfying L_i \leq x \leq R_i, the number of times it has been painted increased by 1.

Parts that have been painted K or more times are considered sufficiently thick and pass inspection, while parts painted fewer than K times are too thin and fail.

After all operations are completed, find the total length of the set of all points that have been painted K or more times (that is, the sum of the lengths of each interval that constitutes this set).

For example, if the set of all points painted K or more times is the union of intervals [1, 5] and [7, 9], the answer is (5 - 1) + (9 - 7) = 6.

Note that since all L_i and R_i are integers, the boundaries where the paint count changes occur only at integer coordinates. Therefore, the answer is always an integer.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq N
  • 0 \leq L_i < R_i \leq 10^9
  • All input values are integers

Input

N K
L_1 R_1
L_2 R_2
\vdots
L_N R_N
  • The first line contains an integer N representing the number of painting operations and an integer K representing the threshold number of coats required to pass inspection, separated by a space.
  • The i-th of the following N lines (1 \leq i \leq N) contains the left endpoint L_i and right endpoint R_i of the interval painted in the i-th operation, separated by a space.

Output

Output the total length of the set of all points painted K or more times, as an integer on a single line.

Sample Input 1

3 2
1 5
3 7
6 9

Sample Output 1

3

Sample Input 2

2 2
0 3
5 8

Sample Output 2

0

Sample Input 3

8 3
0 10
2 8
4 12
1 6
5 15
7 9
3 11
10 14

Sample Output 3

10

Sample Input 4

15 4
0 100
10 90
20 80
30 70
40 60
5 50
15 85
25 75
35 65
45 55
0 30
50 100
60 95
70 88
3 47

Sample Output 4

85

Sample Input 5

1 1
0 1000000000

Sample Output 5

1000000000