该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

[AdditionalFile2071.zip](file://AdditionalFile2071.zip?type=additional_file)

#2071. 「JSOI2016」最佳团体

标签: 传统 | 时间限制: 1000 ms | 内存限制: 256 MiB |

题目描述

JSOI 信息学代表队一共有 $N$ 名候选人，这些候选人从 $1$ 到 $N$ 编号。方便起见，JYY 的编号是 $0$ 号。每个候选人都由一位编号比他小的候选人 $R_i$ 推荐。如果 $R_i=0$，则说明这个候选人是 JYY 自己看上的。

为了保证团队的和谐，JYY 需要保证，如果招募了候选人 $i$，那么候选人 $R_i$ 也一定需要在团队中。当然了，JYY 自己总是在团队里的。每一个候选人都有一个战斗值 $P_i$，也有一个招募费用 $S_i$。JYY 希望招募 $K$ 个候选人（JYY 自己不算），组成一个性价比最高的团队。也就是，这 $K$ 个被 JYY 选择的候选人的总战斗值与总招募费用的比值最大。

输入格式

输入一行包含两个正整数 $K$ 和 $N$。
接下来 $N$ 行，其中第 $i$ 行包含三个整数 $S_i,P_i,R_i$ 表示候选人 $i$ 的招募费用，战斗值和推荐人编号。

输出格式

输出一行一个实数，表示最佳比值。答案保留三位小数。

样例

输入

1 2
1000 1 0
1 1000 1

输出

0.001

数据范围与提示

对于 $100\%$ 的数据满足 $1 \leq K \leq N \leq 2500,\ 0< S_i,P_i \leq 10^4,\ 0 \leq R_i<i$。