UpCoder 正在寻找最优秀的员工组建一个团队，负责设计他们全新的改进版网站，他们希望你能帮助他们组建这个团队。共有 $n$ 名潜在候选人。CEO 是 0 号员工，候选人的编号从 $1$ 到 $n$。每名候选人都由一名编号较小的员工推荐。除了员工编号外，每名候选人还可以用三个数字来描述：他们的协商薪水、预期生产力以及推荐他们的员工编号。

你希望从总共 $n$ 名候选人中选出恰好 $k$ 名候选人组成团队。这些候选人能提供的总价值为他们生产力之和除以他们薪水之和。请注意，只有当候选人的推荐人也属于该团队，或者推荐人是 CEO 时，你才能将该候选人加入团队。因此，你选出的候选人中至少要有一人是由 CEO 推荐的。CEO 负责公司的业务方面，因此他/她不计入选出的 $k$ 名团队成员中。

在满足这些约束条件的情况下，求出你的团队所能提供的最大总价值。

输入格式

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

输出格式

输出一个实数，表示在满足题目约束的情况下，组建 $k$ 人团队所能达到的最大总价值。将此数字输出到小数点后三位，四舍五入（标准 $5$ 进 $4$ 舍）。

样例

样例输入 1

1 2
1000 1 0
1 1000 1

样例输出 1

0.001

样例输入 2

2 3
1 100 0
1 200 0
1 300 0

样例输出 2

250.000