Maximizing Team Efficiency

The JSOI Informatics team has \(N\) candidates numbered from \(1\) to \(N\). For convenience, JYY is assigned number \(0\). Every candidate \(i\) is recommended by a candidate with a smaller number \(R_i\). If \(R_i=0\), candidate \(i\) is directly favored by JYY.

To ensure team harmony, if candidate \(i\) is recruited then candidate \(R_i\) must also be in the team. (JYY is always in the team.) Each candidate \(i\) carries a battle value \(P_i\) and a recruitment cost \(S_i\). JYY wishes to recruit exactly \(K\) candidates (excluding himself) so that the ratio \[ \frac{\text{total battle value}}{\text{total recruitment cost}} \] is maximized.

Note that the recruiting condition implies that if a candidate is selected then all of his ancestors in the recommendation tree (up to JYY) must also be selected. As a result, the \(K\) candidates must form a subtree (rooted at JYY) with exactly \(K\) nodes (apart from JYY).

Your task is to compute the maximum possible ratio. Output the answer as a floating-point number rounded to six decimal places.

inputFormat

The first line contains two integers \(N\) and \(K\) \((1 \le K \le N)\) which indicate the number of candidates and the number of candidates to be recruited (excluding JYY).

Then \(N\) lines follow. The \(i\)-th line (for \(1 \le i \le N\)) contains three integers \(R_i\), \(P_i\), and \(S_i\) where \(R_i=0\) or \(1 \le R_i < i\), and \(P_i, S_i \ge 1\). \(R_i\) is the recommender of candidate \(i\), \(P_i\) is his battle value, and \(S_i\) is his recruitment cost.

outputFormat

Output the maximum ratio \(\frac{\text{total battle value}}{\text{total recruitment cost}}\) achievable by selecting exactly \(K\) candidates (while satisfying the recruiting rules) as a floating-point number with 6 digits after the decimal point.

sample

3 2
0 10 5
1 5 1
1 6 2

2.500000