菜品研发
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目描述
伞伞正在厨房研发新的菜品。厨房共有 种食材,第 种食材有 个。伞伞每研发一道菜品,需要消耗第 种食材 个,除此之外,伞伞还有 包 “魔法粉”。每包魔法粉都可以变成任意种类的食材。消耗 包魔法粉可以获得 个相同种类的食材。现在伞伞想知道,他最多可以研发多少道菜品。
输入格式
从文件 dish.in 读入数据。
第一行包含三个整数 ,表示食材数、魔法粉数、消耗一包魔法粉可以获得的食材数量。
接下来一行 个整数 ,表示厨房里第 种食材的数量。
接下来一行 个整数 ,表示研发一道菜品需要消耗第 种食材的数量。
输出格式
输出到文件 dish.out。
一行一个整数,表示最多可以研发多少道菜品。
3 1 1
11 3 16
2 1 4
4
4 3 1
11 12 14 20
4 3 5 6
3
4 3 6
11 12 14 20
4 3 5 6
4
1 1000000000 1000000000
1
1
1000000000000000001
3 10 2
10 20 30
3 5 7
5
样例 6
样例 7
样例 8
样例 9
样例 10
见 dish10.in 与 dish10.ans。
数据规模与约定
下发文件分别对应子任务 。
有合理的子任务依赖。
| 子任务编号 | 特殊性质 | 分值 | |
|---|---|---|---|
| 无 | |||
| 保证答案不超过 | |||
| (每包只变出 个) | |||
| (每道菜每种食材只需 个) | |||
| 无 | |||
对于 的数据:保证 $1 \leq n \leq 2 \times 10^5,1 \leq k,c,a_i,b_i \leq 10^9$。
时空限制: 秒 / 。
提示
答案可能超过 ,请使用 long long。