题目描述

这是一道模板题。

给你 $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 x_i}{\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$ 位。

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

0.4667

3 2
5 0 2
5 1 6

0.8333

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

0.4923

数据范围与提示

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