手伝いとお小遣い

2 secs 1024 MB
shinnshinn's icon shinnshinn

問題

子供が家で家事を手伝いたいと思っています。家事はNN種類あり、各家事iiには労力EiE_iと報酬としてもらえるお小遣いPiP_iが定められています。子供は正確にKK個の家事を選んで手伝うことにしました。

子供の目的は、選んだKK個の家事の労力の総和とお小遣いの総和の比率、PiEi\displaystyle\frac{\sum P_i}{\sum E_i} を最大化することです。この最大値を求めてください。

制約

  • 1KN1041 \leqq K \leqq N \leqq 10^{4}
  • 1Ei1081 \leqq E_i \leqq 10^{8}
  • 1Pi1081 \leqq P_i \leqq 10^{8}
  • 入力はすべて整数

入力

N K
E_1 E_2 ... E_N
P_1 P_2 ... P_N

出力

最大値を出力してください。相対誤差が 10510^{-5} 以下 または 絶対誤差が 10510^{-5} 以下であれば正解として扱われる。


入力例1

4 3
2 4 6 7
3 4 1 4

出力例1

0.846153846154

1,2,4番目の手伝いを選ぶと、3+4+42+4+7=0.84615384615...\displaystyle\frac{3 + 4 + 4}{2 + 4 + 7} = 0.84615384615...となりこれが最適です。

入力例2

7 3
10 93 19 48 50 29 42
14 58 24 27 83 29 88

出力例2

1.813725490196

提出


Go (1.21)