Those Russian Hackers

During the election, which lasts $k \cdot n$ seconds, time is discrete. There are $k \cdot n$ units of time numbered from 0 to $k \cdot n - 1$, and every event lasts an integer number of these units.

The election is split into $k$ equal time frames: seconds 0 to $n - 1$, seconds $n$ to $2n - 1$, and so on. The security program starts with the election and performs one security check in each frame. Each check lasts exactly one second. The second of each check is chosen at random: a check happens during second $i \cdot n + j$ with probability $p_j$. Checks in different frames are independent of each other.

You may log in at any second, and then you spend a random amount of hacking time. The job takes $j$ seconds with probability $q_j$, independent of the security checks. You can log in only once, so after you log in you must finish the job.

The security program sends you a message each time a check finishes. You may log in right after such a message, at the next second. If a security check happens during any second when you are logged in, the election is interrupted and you fail. If you do not finish your job before the election ends, you also fail.

Find the success probability of the best strategy.

The first line contains two integers $n$ and $k$ ($2 \leq n \leq 300\,000$, $1 \leq k \leq 300\,000$), the length of each time frame and the number of security checks.

The second line contains $n$ real values $p_0, p_1, \ldots, p_{n-1}$ ($0 \leq p_i \leq 1$, $\sum_{i=0}^{n-1} p_i = 1$), the distribution of the exact second of a security check within its frame.

The third line contains $2n - 2$ real values $q_1, q_2, \ldots, q_{2n-2}$ ($0 \leq q_i \leq 1$, $\sum_{i=1}^{2n-2} q_i = 1$), the distribution of the hacking time.

All probabilities are given with at most six digits after the decimal point.

Print the maximum probability of success. Your answer is accepted if its absolute error does not exceed $10^{-6}$.

In the first sample, there is only one security check. The best strategy is to wait until the check finishes, then log in and try to hack before time runs out. The success probability is $0.5 \cdot (0.75 + 0.25) + 0.25 \cdot 0.75 + 0.25 \cdot 0 = 0.6875$.

In the second sample, the hacking time is always exactly four seconds. You must log in at second 1 and finish by second 4 no matter what the checks do. You succeed only if the first check happens at second 0 and the second check happens at second 5, so the probability is $0.3 \cdot 0.3 = 0.09$.

In the third sample, the best strategy is to always start hacking at second 1, which gives a success probability of 0.8.