← 返回题目列表

Codeforces · 985/E

E. 铅笔和盒子

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

米什卡收到了一份彩色铅笔作为生日礼物!不幸的是,他生活在一个单色世界,一切都是相同的颜色,只有饱和度不同。该包可以表示为 n 个整数的序列 a1, a2, ..., an - 每支铅笔的颜色饱和度。现在米什卡想要把包里的所有乱七八糟的东西整理好。他有无数的空盒子来做到这一点。他想以这样的方式填写一些框:

- 每支铅笔都属于一个盒子;
- 每个非空盒子里至少有 k 支铅笔;
- 如果铅笔 i 和 j 属于同一个盒子,则 |ai - aj| ≤ d,其中 |x|表示x的绝对值。请注意,相反的是可选的,可以有铅笔 i 和 j 使得 |ai - aj| ≤ d 并且它们属于不同的盒子。

帮助米什卡确定是否可以将所有铅笔分发到盒子里。如果存在这样的分布,则打印“YES”。否则打印“NO”。

输入

第一行包含三个整数 n、k 和 d (1 ≤ k ≤ n ≤ 5·105, 0 ≤ d ≤ 109) — 分别是铅笔的数量、任何非空盒子的最小尺寸以及同一盒子中任何一对铅笔之间的最大饱和度差异。

第二行包含 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ 109) — 每支铅笔的颜色饱和度。

输出

如果可以将所有铅笔分发到盒子中并满足所有条件,请打印“是”。否则打印“NO”。

示例

输入 #1

6 3 10
7 2 7 7 4 2

输出 #1

YES

输入 #2

6 2 3
4 5 3 13 4 10

输出 #2

YES

输入 #3

3 2 5
10 16 22

输出 #3

NO

注意

在第一个示例中,可以将铅笔分配到 2 个盒子中,每个盒子中有 3 支铅笔,可以任意分配。并且你也可以将所有铅笔放入同一个盒子中,其中任何一对的差异都不会超过10。

在第二个示例中,您可以将饱和度 [4, 5, 3, 4] 的铅笔分成 2 个大小为 2 的盒子,并将剩余的放入另一个盒子中。