Background

Special for beginners, ^_^

Description

这是一道模板题。

给你 $n$ 个物品，每个物品有两个属性 $a_i$ 和 $b_i$，求一组解 $x_i$（$1 \leq i \leq n$，$x_i = 0$ 或 $1$）使

$$\frac{\sum_{i=1}^n a_i \times x_i}{\sum_{i=1}^n b_i \times x_i}$$

最大，且恰好有 $k$ 个 $x_i$ 为 $1$。

请求出这个最大值。如果你的答案与标准答案的绝对误差在 $5 \times 10^{-5}$ 以内，你的答案就被视为是正确答案。

Format

Input

第一行两个数，$n, k$。
第二行 $n$ 个数，依次表示 $a_1, a_2, \dots, a_n$。
第三行 $n$ 个数，依次表示 $b_1, b_2, \dots, b_n$。

Output

一行，一个实数。

Samples

5 3
1 2 4 1 2
4 3 9 3 7

0.4666666667

3 2
5 0 2
5 1 6

0.8333333333

10 6
1 5 3 7 2 8 5 4 2 6
15 35 12 12 9 15 7 7 13 15

0.4923076923

Limitation

1s, 1024KiB for each test case.

数据范围：

$1 \leq k \leq n \leq 10^5$，$0 \leq a_i \leq b_i$，$1 \leq b_i \leq 10^6$。