149 01 分数规划

这是一道模板题。

给你 $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$。

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

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

一行，一个实数。

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