CF48F.Snow sellers

The New Year celebrations in Berland last n days. Only this year the winter is snowless, that’s why the winter celebrations’ organizers should buy artificial snow. There are m snow selling companies in Berland. Every day the i-th company produces w__i cubic meters of snow. Next day the snow thaws and the company has to produce w__i cubic meters of snow again. During the celebration new year discounts are on, that’s why the snow cost decreases every day. It is known that on the first day the total cost of all the snow produced by the i-th company is equal to c__i bourles. Every day this total cost decreases by a__i bourles, i.e. on the second day it is equal to c__i - a__i,and on the third day — to c__i - 2_a__i_, and so on. It is known that for one company the cost of the snow produced by it does not get negative or equal to zero. You have to organize the snow purchase so as to buy every day exactly W snow cubic meters. At that it is not necessary to buy from any company all the snow produced by it. If you buy n__i cubic meters of snow (0 ≤ n__i ≤ w__i, the number n__i is not necessarily integer!) from the i-th company at one of the days when the cost of its snow is equal to s__i, then its price will total to bourles. During one day one can buy the snow from several companies. In different days one can buy the snow from different companies. It is required to make the purchases so as to spend as little money as possible. It is guaranteed that the snow produced by the companies will be enough.

贝兰德的新年庆祝活动持续 $n$ 天。今年冬天没有降雪，因此冬季庆祝活动的组织者需要购买人造雪。贝兰德共有 $m$ 家售雪公司。第 $i$ 家公司每天生产 $w_i$ 立方米的雪；次日积雪融化，该公司需再次生产 $w_i$ 立方米的雪。庆祝期间正值新年促销，因此雪的价格逐日下降。已知：第 $1$ 天，第 $i$ 家公司所产全部雪的总价格为 $c_i$ 博尔勒（bourles）；此后每天该总价格减少 $a_i$ 博尔勒，即第 $2$ 天为 $c_i - a_i$，第 $3$ 天为 $c_i - 2a_i$，依此类推。已知对任意一家公司，其每日所产雪的总价格均严格大于零（不会变为负数或零）。
你须安排购雪方案，使得每天恰好购买 $W$ 立方米的雪。购买时无需从某家公司购入其当日生产的全部雪量。若在某一天（此时第 $i$ 家公司所产雪的单价为 $s_i$）向第 $i$ 家公司购买 $n_i$ 立方米的雪（其中 $0 \leq n_i \leq w_i$，且 $n_i$ 不必为整数），则此次购买的费用总计为 博尔勒。
同一天内可向多家公司购雪；不同天内可向不同公司购雪。
目标是制定购雪方案，使总花费最小。
题目保证所有公司所能提供的雪总量足以满足需求。

The first line contains integers n, m and W (1 ≤ n ≤ 100, 1 ≤ m ≤ 500000, 1 ≤ W ≤ 109) which represent the number of days, the number of companies and the amount of snow that needs to be purchased on every one of the n days. The second line contains m integers w__i. The third line contains m integers c__i. The fourth line contains m integers a__i. All the numbers are strictly positive and do not exceed 109. For all the i the inequation c__i - (n - 1)a__i > 0 holds true.

第一行包含三个整数 $n$、$m$ 和 $W$（$1 ≤ n ≤ 100$，$1 ≤ m ≤ 500000$，$1 ≤ W ≤ 10^9$），分别表示天数、公司数量以及每天（共 $n$ 天）所需采购的雪量。
第二行包含 $m$ 个整数 $w_i$。
第三行包含 $m$ 个整数 $c_i$。
第四行包含 $m$ 个整数 $a_i$。
所有数字均为严格正数，且均不超过 $10^9$。对所有 $i$，不等式 $c_i - (n - 1)a_i > 0$ 成立。

Print a single number — the answer to the given problem. Print the answer in the format with the decimal point (even if the answer is integer, it must contain the decimal point), without "e" and without leading zeroes. The answer should differ with the right one by no more than 10 - 9.

输出一个数字——即该问题的答案。答案需以带小数点的格式输出（即使答案为整数，也必须包含小数点），不得使用科学计数法（即不能含 "e"），且不得有前导零。输出答案与正确答案的绝对误差不得超过 $10^{-9}$。