#2580. 背包类树形 DP

背包类树形 DP

Description

在一个地图上有NN 座城堡,每座城堡都有一定的宝物。在每次游戏中都允许攻克MM 个城堡并获得里面的宝物。但有些城堡不可以直接攻克,要攻克这些城堡,必须先攻克其他某个特定的城堡。计算攻克MM 个城堡最多可以获得的宝物数量。

Input

每个测试实例都首先包括两个整数NNMM 11MM NN220000。接下来的NN 行,每行都包括两个整数aabb 。在第ii 行中,aa表示要攻克第ii 个城堡,则必须先攻克第aa 个城堡,若aa =00,则表示可以直接攻克第ii 个城堡;bb bb00表示第ii 个城堡的宝物数量。当NN=00MM =00时输入结束。

Output

对每个测试实例,都单行输出攻克MM 个城堡最多可以获得的宝物数量。

Samples

3 2
0 1
0 2
0 3
7 4
2 2
0 1
0 4
2 1
7 1
7 6
2 2
0 0
5
13

来源

HDU1561