说明

有$n$名工人。 给定两个数组 quality 和 wage ，其中，quality[i] 表示第 $i$ 名工人的工作质量，其最低期望工资为 wage[i]

现在我们想雇佣 $k$ 名工人组成一个工资组。在雇佣 一组$k$ 名工人时，我们必须按照下述规则向他们支付工资：

• 对工资组中的每名工人，应当按其工作质量与同组其他工人的工作质量的比例来支付工资。
• 工资组中的每名工人至少应当得到他们的最低期望工资。

给定整数$k$ ，返回 组成满足上述条件的付费群体所需的最小金额 。在实际答案的$10^{-5}$ 以内的答案将被接受。

输入格式

第一行一个整数$n$,表示共有$n$名工人。

第二行，一个数组$n$个元素，表示数组 quality

第三行，一个数组$n$个元素，表示数组 wage

第四行，一个整数$k$，

输出格式

输出付费群体所需的最小金额，结果保留5位小数

3
10 20 5
70 50 30
2

105.00000

解释：

我们向 0 号工人支付 70，向 2 号工人支付 35。

5
3 1 10 10 1
4 8 2 2 7
3

30.66667

解释：

我们向 0 号工人支付 4，向 2 号和 3 号分别支付 13.33333。

数据范围

$n == quality.length == wage.length$

$1 \leqslant k \leqslant n \leqslant 10^4$

$1 \leqslant quality[i], wage[i] \leqslant 10^4$

来源

LeetCode 857