CF633E.Startup Funding

An e-commerce startup pitches to the investors to get funding. They have been functional for n weeks now and also have a website!

For each week they know the number of unique visitors during this week v__i and the revenue c__i. To evaluate the potential of the startup at some range of weeks from l to r inclusive investors use the minimum among the maximum number of visitors multiplied by 100 and the minimum revenue during this period, that is:

The truth is that investors have no idea how to efficiently evaluate the startup, so they are going to pick some k random distinct weeks l__i and give them to managers of the startup. For each l__i they should pick some r__i ≥ l__i and report maximum number of visitors and minimum revenue during this period.

Then, investors will calculate the potential of the startup for each of these ranges and take minimum value of p(l__i, r__i) as the total evaluation grade of the startup. Assuming that managers of the startup always report the optimal values of r__i for some particular l__i, i.e., the value such that the resulting grade of the startup is maximized, what is the expected resulting grade of the startup?

一家电子商务初创公司向投资者进行融资路演。该公司目前已运营了 n 周，并已上线网站！

对于每一周，他们已知该周的独立访客数 v__i 和收入 c__i。为评估初创公司在某一周段（从第 l 周到第 r 周，含端点）的发展潜力，投资者采用如下指标：

事实上，投资者并不清楚如何高效地评估该初创公司，因此他们将随机选取 k 个互不相同的周次 l__i，并将这些周次交给初创公司的管理者。对每个 l__i，管理者需选定某个 r__i ≥ l__i，并报告该区间内访客数的最大值与收入的最小值。

随后，投资者将针对每个这样的区间计算初创公司的潜力值，并取所有 p(l__i, r__i) 中的最小值作为该初创公司的最终综合评估等级。假设初创公司的管理者总能为给定的每个 l__i 选择最优的 r__i（即使得最终评估等级最大化的 r__i），那么该初创公司的期望最终评估等级是多少？

The first line of the input contains two integers n and k (1 ≤ k ≤ n ≤ 1 000 000).

The second line contains n integers v__i (1 ≤ v__i ≤ 107) — the number of unique visitors during each week.

The third line contains n integers c__i (1 ≤ c__i ≤ 107) —the revenue for each week.

输入的第一行包含两个整数 $n$ 和 $k$（$1 ≤ k ≤ n ≤ 1 000 000$）。

第二行包含 $n$ 个整数 $v_i$（$1 ≤ v_i ≤ 10^7$）—— 每周的唯一访客数量。

第三行包含 $n$ 个整数 $c_i$（$1 ≤ c_i ≤ 10^7$）—— 每周的收入。

Print a single real value — the expected grade of the startup. Your answer will be considered correct if its absolute or relative error does not exceed 10 - 6.

Namely: let's assume that your answer is a, and the answer of the jury is b. The checker program will consider your answer correct, if .

输出一个实数值——该创业公司的预期成绩。若你的答案的绝对或相对误差不超过 $10^{-6}$，则视为正确。

具体而言：假设你的答案为 $a$，评测组的答案为 $b$。当满足 时，评测程序将判定你的答案正确。

Consider the first sample.

If the investors ask for l__i = 1 onwards, startup will choose r__i = 1, such that max number of visitors is 3 and minimum revenue is 300. Thus, potential in this case is min(3·100, 300) = 300.

If the investors ask for l__i = 2 onwards, startup will choose r__i = 3, such that max number of visitors is 2 and minimum revenue is 200. Thus, potential in this case is min(2·100, 200) = 200.

If the investors ask for l__i = 3 onwards, startup will choose r__i = 3, such that max number of visitors is 1 and minimum revenue is 300. Thus, potential in this case is min(1·100, 300) = 100.

We have to choose a set of size 2 equi-probably and take minimum of each. The possible sets here are : {200, 300},{100, 300},{100, 200}, effectively the set of possible values as perceived by investors equi-probably: {200, 100, 100}. Thus, the expected value is (100 + 200 + 100) / 3 = 133.(3).

考虑第一个样例。

如果投资者要求从第 $l_i = 1$ 天开始，初创公司会选择 $r_i = 1$，使得访客数最大值为 $3$，最小收入为 $300$。因此，此情况下的潜力为 $\min(3 \cdot 100,\, 300) = 300$。

如果投资者要求从第 $l_i = 2$ 天开始，初创公司会选择 $r_i = 3$，使得访客数最大值为 $2$，最小收入为 $200$。因此，此情况下的潜力为 $\min(2 \cdot 100,\, 200) = 200$。

如果投资者要求从第 $l_i = 3$ 天开始，初创公司会选择 $r_i = 3$，使得访客数最大值为 $1$，最小收入为 $300$。因此，此情况下的潜力为 $\min(1 \cdot 100,\, 300) = 100$。

我们需要等概率地从中选出一个大小为 $2$ 的子集，并对每个子集取其中的最小值。此处所有可能的子集为：$\{200,\, 300\}$、$\{100,\, 300\}$、$\{100,\, 200\}$，即投资者等概率感知到的可能潜力值集合为：$\{200,\, 100,\, 100\}$。因此，期望值为 $(100 + 200 + 100) / 3 = 133.\overline{3}$。