Description

There are $N$ candidates in the JSOI informatics team, numbered from $1$ to $N$. For convenience, JYY is numbered $0$. Each candidate $i$ is recommended by a candidate with a smaller number $R_i$. If $R_i = 0$, it means this candidate was picked by JYY himself.

To ensure team harmony, JYY requires that if candidate $i$ is recruited, then candidate $R_i$ must also be in the team. JYY is always in the team. Each candidate has a combat power $P_i$ and a recruitment cost $S_i$. JYY wants to recruit $K$ candidates (excluding JYY) to form the team with the best ratio; that is, maximize the ratio of the total combat power to the total recruitment cost of these $K$ selected candidates.

Input Format

The first line contains two positive integers $K$ and $N$.

The $i$-th of the next $N$ lines contains three integers $S_i$, $P_i$, $R_i$, indicating candidate $i$’s recruitment cost, combat power, and recommender number.

Output Format

Print one real number, the best ratio. The answer should be rounded to three decimal places.

1 2
1000 1 0
1 1000 1

0.001

Hint

For $100\%$ of the testdata, $1 \le K \le N \le 2500$, $0 < S_i, P_i \le 10^4$, $0 \le R_i < i$.

Translated by ChatGPT 5