프로그래밍 팀

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$는 이 후보의 사원 번호).

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