← 返回题目列表

AtCoder · awc0026_d

D. 重新粉刷墙壁

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

分数: 366 分

问题陈述

高桥正在用油漆粉刷一面长长的水平墙。

墙延伸到整条数轴,最初,数轴上的每个点都已被绘制 0 次。高桥表演 N 喷漆作业。 i第次操作 (1 \leq i \leq N),他画了区间 [L_i, R_i] (其中 L_i < R_i)一次。也就是说,对于每一个对应实数的点 x 满意 L_i \leq x \leq R_i,已绘制的次数增加了 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
  • 第一行包含一个整数 N 表示绘画操作的次数和一个整数 K 代表通过检查所需的涂层阈值数量,以空格分隔。
  • 的 i- 以下各项 N 行 (1 \leq i \leq N) 包含左端点 L_i 和右端点 R_i 中绘制的间隔 i第一个操作,以空格分隔。

输出

输出所有绘制点集合的总长度 K 或多次,作为单行上的整数。


示例输入 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