题目描述

UpCoder 正在寻找将其最优秀的员工分配到负责设计全新改进网站的项目团队中，他们希望你帮助组建这个团队。有 $n$ 位潜在候选人。CEO 是员工编号 $0$，候选人被分配了从 $1$ 到 $n$ 的员工编号。每位候选人由一位员工编号更小的员工推荐。每位候选人除了员工编号外，还可以用三个数字来描述：他们协商的薪水、预期的工作效率以及推荐他们的员工编号。

你需要从总共 $n$ 位候选人中恰好选择 $k$ 位加入团队。从这些候选人中获得的总价值等于他们的工作效率之和除以他们的薪水之和。注意，只有当推荐人也属于团队或者是 CEO 时，你才能将候选人分配到团队中。因此，你选择的候选人中至少有一位必须由 CEO 推荐。CEO 处理公司的业务方面，因此她/他不会被计入为团队选择的 $k$ 位候选人中。

请在这些约束条件下，找出你的团队能够提供的最大总价值。

输入格式

每个输入包含单个测试用例。请注意，你的程序可能会在不同输入上多次运行。输入的第一行包含两个空格分隔的整数 $k$ 和 $n$（$1 \leq k \leq n \leq 2{,}500$），其中 $k$ 是你要组建的团队规模，$n$ 是员工候选人的总数。接下来的 $n$ 行，每行包含三个空格分隔的整数，描述一位员工。首先描述员工 $1$，然后是员工 $2$，依此类推。这三个整数是 $s$、$p$ 和 $r$，其中 $s$（$1 \leq s \leq 10{,}000$）是员工的薪水，$p$（$1 \leq p \leq 10{,}000$）是员工的工作效率，$r$（$0 \leq r < i$）是推荐该候选人的员工编号（$i$ 是该候选人的员工编号）。

输出格式

输出一个实数，表示在问题约束条件下，组建一个由 $k$ 名员工组成的团队所能获得的最大总价值。将该数字输出到恰好三位小数，采用四舍五入（标准 $5 \uparrow / 4 \downarrow$ 舍入）。

1 2
1000 1 0
1 1000 1

0.001

2 3
1 100 0
1 200 0
1 300 0

250.000

提示

翻译由 DeepSeek V3.2 完成