【题目描述】

给定两个长度为 $n$ 的序列 ${a_i}, {b_i}$，设 $f(l, r) = \max_{s⊆ [l,r]∩Z}\frac{∑_{i\in s}a_i} {(∑_{i\in s}b_i)+ c}$。
求 $f(i, j) (1 ⩽ i ⩽ j ⩽ n)$ 的第 $k$ 小值。

【输入格式】

从文件 fraction.in 中读入数据。
第一行三个正整数 $n$, $k$, $c$。
第二行 $n$ 个正整数 $a_1, a_2, . . . , a_n$。
第三行 $n$ 个正整数 $b_1, b_2, . . . , b_n$。

【输出格式】

输出到文件 fraction.out 中。
一行一个实数。
当你的答案和标准答案的绝对或相对误差不超过 $10^{-6}$ 时，你的答案被视为正确。

【样例 1 输入】

3 4 12
2 1 5
6 8 6

【样例 1 输出】

0.277777778

【样例 1 解释】

$f(1, 1) = \frac1 9, f(2, 2) = \frac 1 {20}, f(3, 3) = \frac 5 {18}, f(1, 2) = \frac 3 {26}, f(2, 3) = \frac 5{18}, f(3, 3) = \frac 7{24}$，第 4 小为 $\frac 5{18}$ 。
你可以通过修改 $k$ 获得更多小样例。

【数据范围与提示】

对于所有数据，$1 ⩽ n ⩽ 2 × 10^5, 1 ⩽ k ⩽\frac {n(n + 1)}2, 1 ⩽ a_i, b_i ⩽ 10^7, 1 ⩽ c ⩽ 10^{12}, a_i ⩽ b_i$。

样例