题目描述

这是一道模板题。

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

$$\large\frac{\Sigma_{i=1}^{n}a_i\times xi}{\Sigma{i=1}^{n}b_i\times x_i}$$

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

请求出这个最大值。

输入格式

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

输出格式

一行，一个实数，精确到小数点后 $4$ 位。

样例 1

input

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

output

0.4667

样例 2

input

3 2
5 0 2
5 1 6

output

0.8333

样例 3

input

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

output

0.4923

数据范围与提示

$ 1 \leq k \leq n \leq 10^5, $ $ 1 \leq a_i \leq b_i \leq 10^6 $.