无限背包

题目描述

有 $N$ 种物品,每种物品都有无限多个。第 $i$ 种物品的重量为 $A_i$,体积为 $B_i$,价值为 $C_i$。

等级 $X$ 的高桥君可以携带总重量至多为 $X$、总体积至多为 $X$ 的物品。在该条件下,他可以携带任意数量的同种物品,也可以完全不带某些种类的物品。

设 $f(X)$ 为等级 $X$ 的高桥君能携带的物品的最大总价值。可以证明极限 $\displaystyle\lim_{X\to \infty} \frac{f(X)}{X}$ 存在。求这个极限。

输入格式

输入按以下格式从标准输入给出:

$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$ 种物品。此时物品的总价值为 $100000000+100000000=200000000$。这是能达到的最大价值,所以 $\dfrac{f(300000000)}{300000000}=\dfrac{2}{3}$。

也可以证明 $\displaystyle\lim_{X\to \infty} \frac{f(X)}{X}$ 等于 $\dfrac{2}{3}$。因此,答案为 $0.6666666...$。

1
500000000 300000000 123456789

0.2469135780000000

数据范围

• $1\le N\le 2\times 10^5$
• $10^8\le A_i,B_i,C_i \le 10^9$
• 输入中的所有值均为整数。