白天，你只是一名普通的软件工程师，做着日常的软件工程工作：写代码、喝咖啡、参加会议。但到了晚上，你成为了一个人人畏惧，同时又人人崇拜的传奇。你就是著名的俄罗斯黑客！

几个月前，一位重要人物请求你操纵一个遥远小发展中国家的选举。昨天，你登录了本应包含所有选票的选举主服务器，发现选举期间会有一个特殊的安全程序，用于检查是否有人连接到服务器。为了让黑客的工作更加困难，它以以下复杂的方式运行。

整个选举持续 $k \cdot n$ 秒。本题中的时间被视为离散的：共有 $k \cdot n$ 个时间单位，编号从 $0$ 到 $k \cdot n - 1$，任何可能的事件都持续整数个单位时间。

选举时间被划分为 $k$ 个相等的时间帧：第 $0$ 到 $n-1$ 秒，第 $n$ 到 $2n-1$ 秒，以此类推。安全程序在选举开始时立即启动，并将在每个时间帧内执行一次安全检查，共执行 $k$ 次。每次安全检查持续正好一秒。对于每次检查，其发生的具体秒数是根据概率分布 $p_0, p_1, \dots, p_{n-1}$ 随机选择的。形式上，安全检查将在第 $i \cdot n + j$ 秒发生的概率为 $p_j$。不同时间帧的安全检查时间相互独立。

你可以在任何一秒登录系统，然后你需要花费一些时间来执行你的黑客任务。你知道黑客攻击时间取决于许多因素，可以被视为一个由概率分布 $q_1, q_2, \dots, q_{2n-2}$ 定义的整数随机变量。形式上，黑客攻击过程耗时 $j$ 秒的概率为 $q_j$。当然，这个随机变量与安全检查时间是独立的。你只有一次登录尝试机会，所以一旦登录，你就必须完成你的工作。

幸运的是，你成功安装了一个小型后门程序，它会在每次安全检查结束时向你发送一条消息，你可以利用这些信息来规划你的进一步攻击。特别地，你可以选择在消息发出后立即登录，即在安全检查发生的下一秒登录。

如果在你登录选举服务器期间的任何一秒发生了安全检查，选举就会中断，这意味着你失败了。此外，如果你没有在选举时间内完成工作，你也失败了。

如果你选择最佳策略，你成功的概率是多少？

输入格式

第一行包含两个整数 $n$ 和 $k$ ($2 \le n \le 300\,000, 1 \le k \le 300\,000$)：每个安全检查所属的时间帧长度以及安全检查的次数。

第二行包含 $n$ 个空格分隔的实数 $p_0, p_1, \dots, p_{n-1}$ ($0 \le p_i \le 1, \sum_{i=0}^{n-1} p_i = 1$)，定义了安全检查在其时间帧内发生时间的概率分布。

第三行包含 $2n-2$ 个空格分隔的实数 $q_1, q_2, \dots, q_{2n-2}$ ($0 \le q_i \le 1, \sum_{i=1}^{2n-2} q_i = 1$)，定义了你完成选举结果黑客攻击所需时间的概率分布。

所有概率最多给出小数点后六位。

输出格式

输出通过选择适当策略所能获得的最大成功概率。如果你的结果的绝对误差不超过 $10^{-6}$，则被视为正确。

样例

样例输入 1

3 1
0.5 0.25 0.25
0.75 0.25 0.0 0.0

样例输出 1

0.6875000000

样例输入 2

3 2
0.3 0.4 0.3
0.0 0.0 0.0 1.0

样例输出 2

0.0900000000

样例输入 3

3 1
0.5 0.2 0.3
1.0 0.0 0.0 0.0

样例输出 3

0.8000000000

说明

在第一个样例中，只有一次安全检查，最佳策略是等待它结束，然后登录并尝试在时间耗尽前完成黑客攻击。成功的概率等于 $0.5 \cdot (0.75 + 0.25) + 0.25 \cdot 0.75 + 0.25 \cdot 0 = 0.6875$。

在第二个样例中，你知道无论如何你都必须花费正好四秒进行黑客攻击，这意味着你必须在第 $1$ 秒登录并开始攻击，并在第 $4$ 秒结束，而不考虑安全检查。你只有在第一次检查发生在第 $0$ 秒且第二次检查发生在第 $5$ 秒时才会成功。因此成功概率为 $0.3 \cdot 0.3 = 0.09$。

在第三个样例中，最佳策略是始终在第 $1$ 秒进行黑客攻击，这会导致 $0.8$ 的成功概率。