← 返回题目列表

Codeforces · 48/F

F. 卖雪人

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

Berland 的新年庆祝活动持续了 n 天。只是今年冬天没有雪,所以冬季庆典的组织者应该购买人造雪。伯兰有 m 家卖雪公司。第 i 公司每天生产 wi 立方米的雪。第二天雪融化,公司必须再次生产 wi 立方米的雪。过年期间有折扣,所以雪费一天比一天少。已知第一天第 i 个公司生产的所有雪的总成本等于 ci bourles。每天,总成本都会减少 ai bourles,即第二天等于 ci - ai,第三天等于 ci - 2ai,依此类推。众所周知,对于一家公司来说,其生产的雪的成本不会为负或等于零。你必须组织雪的购买,以便每天正好购买W立方米的雪。这样就没有必要从任何公司购买其生产的所有雪。如果您在雪的成本等于 si 的某一天从第 i 个公司购买 ni 立方米的雪(0 ≤ ni ≤ wi,数字 ni 不一定是整数!),那么其价格总计为 $$\frac{n_i s_i}{w_i}$$ bourles。一天之内,人们可以从多家公司购买雪。在不同的日子里,人们可以从不同的公司购买雪。要求购买时花尽可能少的钱。企业生产的雪量有保证。

输入

第一行包含整数n、m和W(1≤n≤100、1≤m≤500000、1≤W≤109),分别代表n天中每一天需要购买的天数、公司数量和雪量。第二行包含m个整数wi。第三行包含m个整数ci。第四行包含m个整数ai。所有数字均为严格正数且不超过 109。对于所有 i,不等式 ci - (n - 1)ai > 0 成立。

输出

打印一个数字——给定问题的答案。以带小数点的格式打印答案(即使答案是整数,也必须包含小数点),不带“e”且不带前导零。答案与正确答案的差异不应超过 10 - 9。

示例

输入 #1

2 3 10
4 4 4
5 5 8
1 2 5

输出 #1

22.000000000000000

输入 #2

100 2 1000000000
999999998 999999999
1000000000 1000000000
1 1

输出 #2

99999995149.999995249999991