1 //状态转移方程：    dp[i][j]=max(dp[i][j],dp[i][j-k]+dp[son[i]][k])    
 2 //                    以第i个城市为起点，攻占j个城市的最大收益
 3 
 4 #include <iostream>
 5 #include <cstring>
 6 using namespace std;
 7 #define MaxSize 205
 8 
 9 int dp[MaxSize][MaxSize];
10 int value[MaxSize];
11 int mapmap[MaxSize][MaxSize];
12 bool vis[MaxSize];
13 int n,m;
14 
15 inline int max(int a,int b){
16     return a>b?a:b;
17 }
18 
19 void dfs(int root){
20     int i,j,k,u;
21     dp[root][1]=value[root];
22     for(i=1;i<=mapmap[root][0];i++){
23         u=mapmap[root][i];//root之后可以选择攻占的城市
24         dfs(u);
25         for(j=m+1;j>0;j--){
26             for(k=1;k+j<=m+1;k++){
27                 dp[root][j+k]=max(dp[root][j+k],dp[root][j]+dp[u][k]);
28             }
29         }
30     }
31 }
32 
33 int main(){
34     //freopen("in.txt","r",stdin);
35     int i;
36     while (scanf("%d%d",&n,&m),(n||m)){
37         for(i=0;i<=n;i++)
38             mapmap[i][0]=0;
39         value[0]=0;
40         for(i=1;i<=n;i++){
41             int a;
42             scanf("%d %d",&a,&value[i]);
43             mapmap[a][0]++;
44             mapmap[a][mapmap[a][0]]=i;
45         }
46         memset(dp,0,sizeof(dp));
47         //问题的关键在于将0作为第零个城堡，价值为零，这样就可以实现大一统！
48         dfs(0);
49         printf("%d\n",dp[0][m+1]);//加入了第零个城堡，则m+1
50     }
51     return 0;
52 }