Bessie는 친구들과 함께 스키 여행을 떠납니다. 산에는 고도가 증가하는 순서대로 번호가 매겨진 N개의 웨이포인트 (1\leq N \leq 10^5)가 있으며, 웨이포인트 1은 산 기슭(가장 낮은 지점)입니다.

1번을 제외한 각 웨이포인트 i>1에는 웨이포인트 i에서 시작하여 웨이포인트 p_i (1\le p_i < i)로 내려가는 스키 코스가 있습니다. 이 코스에는 난이도 d_i (0 \leq d_i \leq 10^9)와 즐거움 e_i (0 \leq e_i \leq 10^9)가 부여되어 있습니다.

Bessie의 M명의 친구들 (1\leq M \leq 10^5)은 각자 처음 시작할 웨이포인트 i를 선택한 후, 코스를 따라 (즉, p_i, 그 다음 p_{p_i}, …) 웨이포인트 1에 도달할 때까지 내려갑니다.

각 친구가 얻는 즐거움은 그들이 밟은 코스들의 즐거움의 총합입니다. 또한, 각 친구는 서로 다른 스킬 레벨 s_j (0 \leq s_j \leq 10^9)와 용기 레벨 c_j (0 \leq c_j \leq 10)를 가지며, 이는 친구들이 시작 웨이포인트를 선택할 때 “자신의 스킬 레벨 s_j보다 큰 난이도의 코스”를 최대 c_j번만 경험할 수 있도록 제한합니다.

각 친구별로, 조건을 만족하면서 얻을 수 있는 최대 즐거움을 구하세요.

#8417 upload 4 done 2 how_to_reg 2

Ski Slope timer 1s memory 1024MB

#8417

Ski Slope 1s 1024MB