Programming Team

Time limit3sMemory limit512 MB

Summary

Choose exactly k candidates from a tree where each pick needs its recommender picked, maximizing total productivity divided by total salary; print the ratio to three decimals.

Level: Hard8 of 10
Topics: Dynamic programming, Tree, Binary search, Greedy
Solved: No attempts yet

Problem

UpCoder is forming a team to build its new website, and you choose the members. There are $n$ candidates, numbered 1 through $n$ . The CEO is employee number 0. Every candidate was recommended by an employee with a smaller number. Besides the employee number, a candidate is described by a salary $s$ , an expected productivity $p$ , and the number $r$ of the employee who recommended them.

You must put exactly $k$ of the $n$ candidates on the team. The total value of the team is the sum of the members' productivities divided by the sum of their salaries. A candidate may join the team only if the employee who recommended them is also on the team, or is the CEO. At least one member is therefore a candidate the CEO recommended. The CEO runs the business side of the company and does not count toward the $k$ members.

Find the largest total value a team can reach under these rules.

Input

The first line has two space separated integers $k$ and $n$ ( $1 \le k \le n \le 2500$ ), where $k$ is the size of the team you must form and $n$ is the number of candidates.

Each of the next $n$ lines describes one employee, employee 1 first, then employee 2, and so on. A line holds three space separated integers $s$ , $p$ and $r$ : the salary $s$ ( $1 \le s \le 10000$ ), the productivity $p$ ( $1 \le p \le 10000$ ), and the number $r$ of the employee who recommended this candidate ( $0 \le r < i$ , where $i$ is this candidate's employee number).

Output

Print the largest total value on one line, to exactly three decimal places. Round the exact value at the fourth decimal place, and round up when the part below the third decimal place is exactly one half.

Examples2

Example 1
Input
```
1 2
1000 1 0
1 1000 1
```
Expected output
```
0.001
```
Example 2
Input
```
2 3
1 100 0
1 200 0
1 300 0
```
Expected output
```
250.000
```