糖果工厂里有 n 种糖果,编号从 1 到 n。第 i 种糖果每天能生产 c_i 个。不同种类的糖果可以同时生产,互不影响。
现在工厂要交付一份订单:一共 a 包糖果,每一包都必须只装同一种糖果,且数量不能少于 b 个。也就是说,一包糖果只能用某一种糖果单独装成,凑够 b 个才能封包;同一种糖果可以装成多包。
工厂从第 0 天开始生产。请求出最少需要多少天才能凑齐这份订单。
第一行三个正整数 n、a、b,分别表示糖果的种类数、订单需要的包数、每包至少需要的数量。
第二行 n 个正整数 c_1, c_2, …, c_n,表示每种糖果每天的生产量。
输出一个整数,表示最少需要的天数。
3 7 3 1 2 10
2
对于所有数据,1 ≤ n ≤ 10^5,1 ≤ a ≤ 10^9,1 ≤ b ≤ 10^9,1 ≤ c_i ≤ 10^9。每个测试点的具体限制见下表:
| 测试点编号 | 约束 |
|---|---|
| 1~3 | a ≤ 10^3,b ≤ 10^3 |
| 4~7 | c_i 可以任意,a ≤ 10^5 |
| 8~10 | 没有其他限制 |