← 返回题目列表

AtCoder · joig2021_d

D. 展览2

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

配点: 100 点

問題文

JOI博物馆有一条从东到西笔直的走廊。 N 显示图片, 它们的编号最大为1 它们的编号最大为 N 。图片 i (1 \leqq i \leqq N)从走廊的西端。 X_i 显示在仪表位置,其值为 V_i 。

预计明天开始在本馆举办“自我展”,预计参观人数众多。在“Egoi展览” M 我打算展出我的画作。

2 当两张图片彼此靠近显示时很难看清,因此请确保满足以下条件。 N-M 移走画作并将它们放在走廊上。 我决定只保留 M 照片。

  • 哪个 2 对于每张图片,位置是 D 确保它们之间至少相距 1 米。

显示中 M 一幅画的最小值是华丽。你把它留在走廊里 M 我想通过精心挑选的画作,让“自我展”尽可能华丽。

N 给定1张图片和留在走廊的图片数量的信息,判断是否有办法留下满足条件的图片,如果有,则创建一个程序,找出“Egoi展览”的光彩最大值。

制約

  • 1 \leqq N \leqq 100\,000.
  • 1 \leqq M \leqq N.
  • 1 \leqq D \leqq 1\,000\,000\,000.
  • 1 \leqq X_i \leqq 1\,000\,000\,000 (1 \leqq i \leqq N).
  • X_i \neq X_j (1 \leqq i < j \leqq N).
  • 1 \leqq V_i \leqq 1\,000\,000\,000 (1 \leqq i \leqq N).
  • 所有输入值都是整数。

小課題

  1. (3 点) M = 1.
  2. (12 点) M = N.
  3. (19 点) N \leqq 15.
  4. (17 点) N \leqq 1\,000,V_i \leqq 2 (1 \leqq i \leqq N).
  5. (22 点) N \leqq 1\,000.
  6. (27 点)没有额外的限制。

评分注意事项

所有提交的内容都将通过评审系统进行评分。

当提交的源代码为与该子作业对应的所有评分输入数据返回正确的结果时,该源代码被认为对于该子作业是正确的。

每次提交的分数是所提交的源代码回答正确的子任务分数的总和。

该作业的分数是此作业所有提交的最高分。

您可以在“提交结果”选项卡上的“我的分数状态”中查看您当前的分数。


入力

输入是按以下格式从标准输入给出的。

N M D
X_1 V_1
X_2 V_2
\vdots
X_N V_N

出力

如果没有办法留下满足条件的图片,则标准输出为 -1 请计算 1 行。 在

如果有办法留下满足条件的图片,则将“Egoi Exhibition”的亮度最大值发送到标准输出。 如果只剩下 1 行。 在


入力例 1

3 1 34
10 250
30 200
50 500

出力例 1

500

絵 3 ,“自我展”的辉煌将是 500 变为。辉煌 它不能大于 500 ,所以500 。

此输入示例是一个小作业。 1, 3, 5, 6 满足约束。


入力例 2

4 4 10
21 160
32 270
11 115
44 205

出力例 2

115

所有画作都可以保留,“自我展”的精彩 115 变为。

此输入示例是一个小作业。 2, 3, 5, 6 满足约束。


入力例 3

4 4 14
21 160
32 270
11 115
44 205

出力例 3

-1

哪个 2 图片之间 14 如果距离超过一米,则无法留下照片。因此,-1 。

此输入示例是一个小作业。 2, 3, 5, 6 满足约束。


入力例 4

6 3 4
4 2
5 2
2 1
9 2
1 1
7 2

出力例 4

1

此输入示例是一个小作业。 3, 4, 5, 6 满足约束。


入力例 5

15 6 129
185 2821
683 3312
101 3406
485 2120
671 1992
869 2555
872 3123
237 2970
351 2374
996 2090
729 2686
375 2219
820 3085
511 3217
924 4229

出力例 5

2219

此输入示例是一个小作业。 3, 5, 6 满足约束。