题目描述

某公司有 $N$ 个职员，编号为 $1$ ∼ $N$。董事长的编号为 $0$。

除了董事长外，每个职员有一个顶头上司，职员 $i$ 的顶头上司是 $S_i$，且顶头上司的编号比职员的编号小，即 $S_i < i$。

现在要召开一场周年庆舞会，主办方准备邀请 $K$ 名职员去参加舞会。

每个职员参加舞会，都会给舞会增加一定的欢乐度。若职员 i 参加舞会，会给舞会增加 $H_i$ 的欢乐度。但是邀请职员是需要支付费用的，邀请职员 $i$ 需要支付 $C_i$ 的费用。

为了不让职员在舞会上过于放肆，主办方决定，如果一个职员被邀请，那么他的顶头上司也一定要被邀请。

董事长自然是要被邀请参会的。而且，邀请董事长是不需要支付费用的。并且，董事长作为董事长，他的参会并不会给舞会带来欢乐度。

秉持着“让每一分钱都发挥出最大价值”的宗旨，主办方希望邀请的 $K$ 名职员给舞会增加的“欢乐度总和”除以“费用总和”的比值最大，求这个最大值。

输入格式

第一行包含两个正整数 $K$ 和 $N$ 。

接下来 $N$ 行，其中第 $i$ 行包含三个整数 $C_i$ , $H_i$ , $S_i$ ,依次表示职员 $i$ 被邀请需要支付的费用，他的快乐指数，他的顶头上司的编号。

输出格式

一个实数，表示答案，保留 $3$ 位小数。

样例输入

1 2
1000 1 0
1 1000 1

样例输出

0.001

数据范围

20% 的数据：$1 ≤ K ≤ N ≤ 20$

100% 的数据：$1 ≤ K ≤ N ≤ 3000$, $0 < H_i, C_i ≤ 10000$, $0 ≤ S_i < i$