配点 : $600$ 点

問題文

$N$ 種類の品物がそれぞれ無限個あります。 $i$ 種類目の品物は重さが $A_i$ 、体積が $B_i$ 、価値が $C_i$ です。

レベル $X$ の高橋君は、重さの合計が $X$ 以下かつ体積の合計が $X$ 以下になるように品物を持つことができます。ここで、高橋君は条件を満たすならば同じ種類の品物を何個でも持つことが可能であり、また選ばない種類の品物があっても構いません。

レベル $X$ の高橋君が持てる品物の価値の合計の最大値を $f(X)$ とするとき、極限 $\displaystyle\lim_{X\to \infty} \frac{f(X)}{X}$ が存在することが証明できます。この値を求めてください。

制約

• $1\leq N\leq 2\times 10^5$
• $10^8\leq A_i,B_i,C_i \leq 10^9$
• 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

$N$

$A_1$ $B_1$ $C_1$

$A_2$ $B_2$ $C_2$

$\vdots$

$A_N$ $B_N$ $C_N$

出力

答えを出力せよ。なお、想定解答との絶対誤差または相対誤差が $10^{-6}$ 以下であれば正解として扱われる。

2
100000000 200000000 100000000
200000000 100000000 100000000

0.6666666666666667

$X=300000000$ のとき、高橋君は重さの合計が $300000000$ 以下かつ体積の合計が $300000000$ 以下になるように品物を持つことができます。

持ち方の一例として、高橋君は $1$ 番目の品物と $2$ 番目の品物を $1$ 個ずつ持つことができます。このとき、品物の価値の合計は $100000000+100000000=200000000$ であり、これが達成可能な価値の最大値なので、$\dfrac{f(300000000)}{300000000}=\dfrac{2}{3}$ です。

また、この入力では極限 $\displaystyle\lim_{X\to \infty} \dfrac{f(X)}{X}$ も $\dfrac{2}{3}$ に一致することが証明できます。よって答えは $0.6666666...$ です。

1
500000000 300000000 123456789

0.2469135780000000