← 返回题目列表

AtCoder · awc0089_e

E. 粉刷栅栏

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

分数: 433 分

问题陈述

Takahashi 已受雇绘制栅栏,其中包括 N 板。板的编号从 1 to N,最初所有板都未上漆。

青木给高桥 M 绘画说明。的 i第一条指令 (1 \leq i \leq M) 是“从板上绘制所有板 L_i 登机 R_i (含)。”如果一块板被多个指令绘制,它最终会处于与绘制一次相同的状态。

由于体力有限,高桥必须完全无视 K 连续指令 M 说明。具体来说,他选择一个整数 s 满意 1 \leq s \leq M - K + 1,忽略 K 的指示 s-第 (s + K - 1)-th(不执行它们),并执行所有剩余的 M - K 说明。

Takahashi 希望通过最佳选择要忽略的指令间隔来最大化最终绘制的木板数量。求出最终被涂漆的木板的最大数量。

约束

  • 1 \leq N \leq 10^9
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq K \leq M
  • 1 \leq L_i \leq R_i \leq N (1 \leq i \leq M)
  • 所有输入均为整数

输入

N M K
L_1 R_1
L_2 R_2
\vdots
L_M R_M

第一行包含板数 N,指令数 M,以及要忽略的连续指令数 K,用空格分隔。的 i-th (1 \leq i \leq M) 以下内容 M 行包含左端点 L_i 和右端点 绘制范围的 R_i 绘制的范围 i- 第一条指令,以空格分隔。

输出

输出最终被绘制的最大板数为整数,当连续 最佳选择要忽略的 K 指令。


示例输入 1

10 4 2
1 3
4 6
2 5
8 10

示例输出 1

7

示例输入 2

8 5 1
1 4
3 6
5 8
2 2
7 7

示例输出 2

8

示例输入 3

50 10 3
1 10
5 15
20 25
12 22
30 40
35 45
2 8
18 19
41 50
10 30

示例输出 3

50

示例输入 4

1000000000 25 7
1 100000
50000 200000
150000 300000
250000 400000
350000 500000
450000 600000
550000 700000
650000 800000
750000 900000
850000 1000000
10000000 20000000
15000000 25000000
24000000 30000000
100000000 200000000
180000000 260000000
250000000 350000000
340000000 420000000
500000000 600000000
590000000 700000000
690000000 800000000
799999999 900000000
850000000 950000000
940000000 1000000000
123456789 123456789
400000000 500000000

示例输出 4

920350003

示例输入 5

1 1 1
1 1

示例输出 5

0