← 返回题目列表

AtCoder · awc0058_c

C. 积雪深度调查

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

分数: 366 分

问题陈述

高桥是气象台的一名工作人员。沿着一条由东向西直线延伸的道路,有 N 观察点,编号 1, 2, \ldots, N 依次,他正在勘察各个点的积雪状况。

最初, 降雪量 在每个点都是 0.

今年冬天,共有 M 降雪。在 i第一场降雪 (1 \leq i \leq M),降雪量增加了 1 从点开始的每一点 L_i 来点 R_i (含)。

换句话说,毕竟 M 降雪已结束,每个点的降雪次数等于该点包含在降雪范围内的总次数。

他的主管青木告诉他“降雪量为 K 或更多需要除雪。”为了制定除雪计划,高桥想要确定降雪量为的点的数量 毕竟 K 或更多 M 降雪已经结束。

查找降雪量为的点数 K 或更多。

约束

  • 1 \leq N \leq 10^6
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq K \leq M
  • 1 \leq L_i \leq R_i \leq N
  • 所有输入值均为整数。

输入

N M K
L_1 R_1
L_2 R_2
\vdots
L_M R_M
  • 第一行包含观察点的数量 N, 降雪次数 M,以及阈值 K 要求除雪,用空格分隔。
  • 的 i第行 (1 \leq i \leq M) 以下内容 M 行包含左端点 L_i 和右端点 R_i 的范围 i第一场降雪,以空格分隔。

输出

在一行中输出降雪量为的点数 K 或更多。


示例输入 1

10 3 2
1 5
3 7
6 10

示例输出 1

5

示例输入 2

5 3 3
1 2
3 4
4 5

示例输出 2

0

示例输入 3

100 5 3
10 50
20 60
30 70
40 80
50 90

示例输出 3

41

示例输入 4

1000000 4 2
1 500000
250001 750000
500001 1000000
1 1000000

示例输出 4

1000000

示例输入 5

1 1 1
1 1

示例输出 5

1