242016 - 糖果工厂

题目描述

糖果工厂里有 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~3a ≤ 10^3,b ≤ 10^3
4~7c_i 可以任意,a ≤ 10^5
8~10没有其他限制
标签
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 3
通过人数 2
金币数量 4 枚
难度 提高


上一题 下一题