题目描述

超市出售 $N$ 件互不相同的商品，编号为 $0,1,\ldots,N-1$。

商品 $i$ 具有：

• 原价 $P_i$；
• 折扣价 $S_i$；
• 一个优惠码 $R_i$。

Tommaso 选择购买某个非空商品子集。结算时，对于每件被购买的商品 $i$：

• 当且仅当购物车中至少有一件商品 $j$ 满足 $R_j=i$ 时，商品 $i$ 按折扣价 $S_i$ 结算；
• 否则，商品 $i$ 按原价 $P_i$ 结算。

同一种商品不能购买多件；多个相同优惠码不会产生额外折扣。商品也可以给自身提供优惠码，即 $R_i=i$。

设所选商品的原价总和为 $P_{\mathrm{tot}}$，实际支付金额为 $P_{\mathrm{discount}}$，折扣百分比为

$$100\left(1-\frac{P_{\mathrm{discount}}}{P_{\mathrm{tot}}}\right).$$

求可以获得的最大折扣百分比。

输入格式

第一行一个整数 $N$。

接下来 $N$ 行，第 $i$ 行包含三个整数 $P_i,S_i,R_i$。

输出格式

输出一个浮点数，表示最大折扣百分比。

当输出与标准答案的绝对误差不超过 $10^{-6}$ 时视为正确。

数据范围

• $1\le N\le 100000$；
• $0\le S_i<P_i\le10000$；
• $0\le R_i<N$。

子任务

子任务	分值	限制
1	0	样例
2	10	对所有 $i$，$R_i=i$
3	15	$N\le20$
4	20	$N\le1000$
5		对所有 $i$，$R_i\le i$
6	25	$R_0=N-1$，且对所有 $i>0$，$R_i=i-1$
7	10	无额外限制

样例 1

输入1
6
100 90 1
10 9 2
90 20 5
100 80 2
40 30 3
100 10 3

输出1
80.000000000

购买商品 $1,2,5$ 时，原价总和为 $200$，实际支付 $P_1+S_2+S_5=40$，折扣为 $80\%$。

样例 2

输入2
5
100 70 1
10 3 2
11 3 3
12 3 1
10 9 4

输出2
72.727272727