프로그래밍 팀

시간 제한3초메모리 제한512 MB

요약

추천한 직원이 팀에 있어야 한다는 조건 아래 트리에서 정확히 k명을 골라 생산성 합을 급여 합으로 나눈 값을 최대로 만들고, 소수 셋째 자리까지 출력한다.

난이도: 어려움10점 중 8점
유형: 동적 계획법, 트리, 이분 탐색, 그리디
정답자: 아직 제출이 없습니다

문제

UpCoder는 새 웹사이트를 만들 팀을 꾸리려 한다. 후보는 $n$ 명이고 사원 번호는 1번부터 $n$ 번까지다. CEO의 사원 번호는 0번이다. 각 후보는 자기보다 번호가 작은 사원의 추천을 받았다. 후보 한 명은 사원 번호 외에 연봉 $s$ , 기대 생산성 $p$ , 자신을 추천한 사원의 번호 $r$ 로 나타낸다.

후보 $n$ 명 중에서 정확히 $k$ 명을 팀에 넣어야 한다. 팀의 총 가치는 팀원 생산성의 합을 팀원 연봉의 합으로 나눈 값이다. 어떤 후보를 팀에 넣으려면 그 후보를 추천한 사원도 팀에 있어야 한다. 추천한 사원이 CEO이면 이 조건은 이미 만족한다. 그래서 팀원 중 적어도 한 명은 CEO가 추천한 후보다. CEO는 경영을 맡으므로 뽑는 $k$ 명에는 들어가지 않는다.

이 조건을 지키면서 만들 수 있는 팀의 최대 총 가치를 구하라.

입력

첫째 줄에 정수 $k$ 와 $n$ 이 공백으로 구분되어 주어진다 ( $1 \le k \le n \le 2500$ ). $k$ 는 뽑아야 하는 팀원 수, $n$ 은 후보 수다.

다음 $n$ 개 줄에는 사원 한 명의 정보가 사원 1번부터 사원 $n$ 번까지 순서대로 주어진다. 각 줄에는 정수 $s$ , $p$ , $r$ 이 공백으로 구분되어 주어진다. $s$ 는 연봉 ( $1 \le s \le 10000$ ), $p$ 는 생산성 ( $1 \le p \le 10000$ ), $r$ 은 이 후보를 추천한 사원의 번호다 ( $0 \le r < i$ , $i$ 는 이 후보의 사원 번호).

출력

팀의 최대 총 가치를 소수점 아래 셋째 자리까지 한 줄에 출력한다. 정확한 값을 소수점 아래 넷째 자리에서 반올림하되, 넷째 자리 아래가 정확히 절반이면 올린다.

예제2

예제 1
입력
```
1 2
1000 1 0
1 1000 1
```
예상 출력
```
0.001
```
예제 2
입력
```
2 3
1 100 0
1 200 0
1 300 0
```
예상 출력
```
250.000
```