Problem1048--#2071. 「JSOI2016」最佳团体

1048: #2071. 「JSOI2016」最佳团体

Time Limit: 1 Sec  Memory Limit: 256 MB
Submit: 0  Solved: 0
[Submit] [Status] [Web Board] [Creator:]

Description

JSOI 信息学代表队一共有 NNN 名候选人,这些候选人从 111NNN 编号。方便起见,JYY 的编号是 000 号。每个候选人都由一位编号比他小的候选人 RiR_iRi 推荐。如果 Ri=0R_i=0Ri=0,则说明这个候选人是 JYY 自己看上的。

为了保证团队的和谐,JYY 需要保证,如果招募了候选人 iii,那么候选人 RiR_iRi 也一定需要在团队中。当然了,JYY 自己总是在团队里的。每一个候选人都有一个战斗值 PiP_iPi,也有一个招募费用 SiS_iSi。JYY 希望招募 KKK 个候选人(JYY 自己不算),组成一个性价比最高的团队。也就是,这 KKK 个被 JYY 选择的候选人的总战斗值与总招募费用的比值最大。

输入格式

输入一行包含两个正整数 KKKNNN
接下来 NNN 行,其中第 iii 行包含三个整数 Si,Pi,RiS_i,P_i,R_iSi,Pi,Ri 表示候选人 iii 的招募费用,战斗值和推荐人编号。

输出格式

输出一行一个实数,表示最佳比值。答案保留三位小数。

样例

样例输入

1 2
1000 1 0
1 1000 1

样例输出

0.001

数据范围与提示

对于 100%100\%100% 的数据满足 1≤K≤N≤2500, 0<Si,Pi≤104, 0≤Ri<i1 \leq K \leq N \leq 2500,\ 0< S_i,P_i \leq 10^4,\ 0 \leq R_i<i 1KN2500, 0<Si,Pi104, 0Ri<i

Source/Category