As the team leader of the JSOI informatics delegation, JYY wants to assemble the best team to represent JSOI in the world championships!
There are $N$ candidates in the JSOI informatics delegation, numbered from $1$ to $N$. For convenience, JYY is numbered $0$.
Each candidate is recommended by another candidate with a smaller index. If $r_i = 0$, it means this candidate was personally selected by JYY.
To ensure harmony within the team, JYY must ensure that if candidate $i$ is recruited, then their recommender $r_i$ must also be in the team. Naturally, JYY is always in the team.
Each candidate has a combat power $p_i$ and a recruitment cost $s_i$.
JYY wishes to recruit $K$ candidates (excluding JYY) to form a team with the highest cost-effectiveness. That is, the ratio of the total combat power to the total recruitment cost of these $K$ candidates selected by JYY should be maximized.
Input
The input contains two integers $K$ and $N$ on the first line.
The next $N$ lines each contain three integers $s_i, p_i, r_i$, representing the recruitment cost, combat power, and recommender index of candidate $i$, respectively.
Output
Output a single real number representing the maximum ratio. The answer should be rounded to three decimal places.
Constraints
- For 30% of the data, $N \le 20$.
- For 50% of the data, $N \le 100$.
- For 100% of the data, $1 \le K \le N \le 2500$, $0 < s_i, p_i \le 10^4$, $0 \le r_i < i$.
Examples
Input 1
1 2 1000 1 0 1 1000 1
Output 1
0.001