题目描述

UpCoder is looking to assign their best employees to a team tasked with designing their new and improved website, and they’re looking to you to help them form the team. There are $n$ potential candidates. The CEO is employee number $0$, and the candidates are all assigned employee numbers ranging from $1$ through $n$. Each candidate is recommended by an employee with a smaller employee number. Each candidate can be described by three numbers (in addition to their employee number): their negotiated salary, their expected productivity, and the number of the employee who recommended them.

You would like to assign exactly $k$ candidates out of the $n$ total candidates to the team. The total value that you can get from these candidates is the sum of their productivities divided by the sum of their salaries. Note that you may only assign a candidate to the team if their recommender is also part of the team, or is the CEO. So, at least one candidate that you assign needs to have the CEO as a reference. The CEO handles the business aspect of the company, so s/he will not be counted as part of the $k$ candidates chosen for the team.

Find the maximum total value your team can provide given these constraints.

输入格式

Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. The first line of the input will consist of two space separated integers $k$ and $n$ ($1 \leq k \leq n \leq 2,500$), where $k$ is the size of the team you must form, and $n$ is the total number of employee candidates. Each of the following $n$ lines will hold three space-separated integers describing an employee. Employee $1$ will be described first, then employee $2$, and so on. The three integers are $s$, $p$ and $r$, where $s$ ($1 \leq s \leq 10,000$) is the employee’s salary, $p$ ($1 \leq p \leq 10,000$) is the employee’s productivity, and $r$ ($0 \leq r < i$) is the employee number of the employee who recommended this candidate (where $i$ is the employee number of this candidate).

输出格式

Output a single real number, which represents the maximum total value you can achieve forming a team of $k$ employees, subject to the constraints of the problem. Output this number to exactly three decimal places, rounded (standard $5 \uparrow / 4 \downarrow$ rounding).

1 2
1000 1 0
1 1000 1

0.001

2 3
1 100 0
1 200 0
1 300 0

250.000