安雅喜欢看恐怖电影。按照恐怖的最佳传统,今晚她将受到 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,因为每一秒最多可以燃烧一根蜡烛,但在鬼魂到来的那一刻,安雅需要三根蜡烛来照亮房间。