← 返回题目列表

Codeforces · 508/C

C. 安雅和鬼魂

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

安雅喜欢看恐怖电影。按照恐怖的最佳传统,今晚她将受到 m 个鬼魂的拜访。 Anya 为参观准备了很多蜡烛,每根蜡烛可以恰好发光 t 秒。女孩点燃一根蜡烛需要一秒钟。更正式地说,Anya 可以花一秒钟点燃一支蜡烛,然后这支蜡烛正好燃烧 t 秒,然后熄灭并且不能再使用。

对于 m 个鬼魂中的每一个,安雅都知道它到来的时间:第 i 次访问将在午夜后 wi 秒内发生,所有 wi 都是不同的。每次访问只持续一秒钟。

Anya 应该使用的最小蜡烛数量是多少,以便在每次访问期间至少燃烧 r 根蜡烛?安雅可以在午夜整数秒后的任何时间(可能是午夜之前)开始点燃蜡烛。这意味着,她可以在午夜之前的整数秒或午夜之后的整数秒,或者换句话说在任何整数时刻开始点燃蜡烛。

输入

第一行包含三个整数 m, t, r (1 ≤ m, t, r ≤ 300),分别代表拜访安雅的鬼魂数量、蜡烛燃烧的持续时间以及每次拜访时应燃烧的最少蜡烛数量。

下一行包含 m 个空格分隔的数字 wi (1 ≤ i ≤ m, 1 ≤ wi ≤ 300),其中第 i 个代表午夜过后第 i 个鬼魂会出现。所有 wi 都是不同的,它们严格按照递增顺序排列。

输出

如果可以在每次访问期间至少燃烧 r 根蜡烛,则打印 Anya 为此需要点燃的最小蜡烛数。

如果不可能,请打印 - 1。

示例

输入 #1

1 8 3
10

输出 #1

3

输入 #2

2 10 1
5 8

输出 #2

1

输入 #3

1 1 3
10

输出 #3

-1

注意

安雅可以在幽灵来访的同一秒开始点燃蜡烛。但这支蜡烛在这次访问中并未被算作燃烧。

点燃一支蜡烛只需要一秒钟,只有在那一秒之后,这根蜡烛才被认为燃烧;这意味着如果 Anya 在 x 时刻开始点燃蜡烛,则蜡烛将从第 x + 1 秒到第 x + t 秒(含)燃烧。

在第一个样本测试中,三根蜡烛就足够了。例如,安雅可以在午夜后的第 3 秒、第 5 秒和第 7 秒开始点亮它们。

在第二个样本测试中,一根蜡烛就足够了。例如,安雅可以在午夜前一秒开始点亮它。

在第三个样本测试中,答案是 - 1,因为每一秒最多可以燃烧一根蜡烛,但在鬼魂到来的那一刻,安雅需要三根蜡烛来照亮房间。