Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

F. Snow sellers

time limit per test

10 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThe 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.

Input

The first line contains integers *n*, *m* and *W* (1 ≤ *n* ≤ 100, 1 ≤ *m* ≤ 500000, 1 ≤ *W* ≤ 10^{9}) 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 10^{9}. For all the *i* the inequation *c*_{i} - (*n* - 1)*a*_{i} > 0 holds true.

Output

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}.

Examples

Input

2 3 10

4 4 4

5 5 8

1 2 5

Output

22.000000000000000

Input

100 2 1000000000

999999998 999999999

1000000000 1000000000

1 1

Output

99999995149.999995249999991

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/26/2017 20:14:57 (c2).

Desktop version, switch to mobile version.

User lists

Name |
---|