题目描述

HDU 1561

后世的历史学家始终不明白为什么修罗王在人类文明存亡的生死攸关之 际给了天顶星人最后的一击，他们从心理学、阴谋论、人性说等方面提出了种种猜 想并为此争论不休。不过我们不必理会他们那些夸夸其谈的酸腐理论,因为全球 著名无厘头导演张某某拍摄的搞笑纪录片《宇宙文明终极战一我和天顶星人不 得不说的故事》里说得很靠谱:修罗王一定是看上天顶星人的宝物了。他是这样 描述的:愚蠢而贪婪的修罗王率领他的邪恶军团攻击由恶心的天顶星人占据的$\red{N}$ 座城堡,每座城堡都有一定的宝物,但由于地理位置原因,有些城堡不能直接攻克， 要攻克这些城堡必须先攻克其他某一个特定的城堡。你能帮修罗王算出要获得尽 量多的宝物应该攻克哪$\red{M}$个城堡吗?

输入格式

每个测试实例首先包括$\red{2}$个整数,$\red{N,M}$。$\red{(1≤}$$\red{M≤}$$\red{N≤}$$\red{200)}$;

在接下来的$\red{N}$行里,每行包括$\red{2}$个整数$\red{a,b}$。在第$\red{i}$行,$\red{a}$代表要攻克第$\red{i}$个城堡必须先攻克第$\red{a}$ 个城,如果$\red{a=0}$则代表可以直接攻克第$\red{i}$个城堡。$\red{b}$代表第$\red{i}$个城堡的宝物数 量,$\red{b≥}$$\red{0}$。当$\red{N=0,M=0}$输入结束。

输出格式

对于每个测试实例,输出一个整数,代表攻克$\red{M}$个城堡所获得的最多宝物的数量。

样例

输入样例

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