文理学院程序设计在线练习


冲锋

Time Limit: 6 Second(s)    Memory Limit: 32 MB

Total Submission(s): 65   Accepted Submission(s): 25
Problem Description

联络完毕的noip群战士们,终于等到了集结的号角。他们蜂拥而上,前往与CCF交锋的战场。
神龟已经准备好了一辆通往战场的列车,按照他的计划,这个列车将能容纳最多C个战士,当然他希望这C个战士总战斗力最强。
不幸的是,由于组织者没有进行合理的秩序安排,战士们在通往战场的列车前挤成了一个大堆;由于时间和空间关系,神龟已经无法对战士按照战斗力重新列队,只能从这一堆人中靠前的挑选战士。
我们可以将noip群战士们挤成的一个堆抽象成一个树的模型;树的根就是列车。一个战士可以进入列车,当且仅当他到列车上的路径中的战士已经全部进入了列车。当然,神龟已经在列车上等待大家了(我们可以认为他,也就是树根,是0号节点),他可是拥有4千万战斗力的勇士呢。
现在请你帮神龟计算,他最多可以带上多少战斗力的勇士。

Input

多组测试,处理到文件结束。
第一行包括两个数n,C,分别代表战士的总人数和列车上能容纳的战士数。
第2~n+1行每行描述了一个战士,分别代表该战士之前的战士(树中的父节点)的编号xi,和这个战士的战斗力wi。
其中:1<=n<=10000,1<=c<=500,0<=xi<=n,0<=wi<=500。

Output

只有一行,列车最多可以带的勇士的战斗力之和。

Sample Input
7 5
2 2
0 1
0 4
2 1
7 1
7 6
2 2
Sample Output
40000013
Hint

提示:对于已经在车上的神龟(神龟也包含在总人数之中),他的战斗力是常量40000000并且不在数据中出现。测试数据中除选中神龟外,其余被选中的编号分别是2-7-6,3。


Source

百度NOIP吧编程挑战赛