1 /*
2 根据先后关系，可以建立一棵树
3 dp[i][j]表示第i个节点选j个的最大值
4 dp[i][j]=max(sigma(dp[c[i][ki]]))
5 sigma(dp[c[i][ki]])表示从i的儿子节点中一共选取j个点的最大值
6 */
7 /*#include <iostream>
8 #include <cstdio>
9 #include <cstring>
10 #include <vector>
11 using namespace std;
12
13 const int maxn=205;
14 int dp[maxn][maxn];
15 int val[maxn],n,m,num[maxn];
16 vector<int> f[maxn];
17 inline int max(int a,int b){return a>b?a:b;}
18
19 void dfs1(int u,int id,int s1,int s2)
20 {
21 if(s1>m+1 || s1>num[u])
22 return ;
23 if(id==f[u].size())
24 {
25 dp[u][s1]=max(dp[u][s1],s2);
26 return ;
27 }
28 for(int i=0;i<=num[f[u][id]];i++)
29 dfs1(u,id+1,s1+i,s2+dp[f[u][id]][i]);
30 return ;
31 }
32
33 void dfs(int u)
34 {
35 if(f[u].size()==0)
36 {
37 dp[u][1]=val[u];num[u]=1;
38 return ;
39 }
40 int temp=0;
41 for(int i=0;i<f[u].size();i++)
42 {
43 int v=f[u][i];
44 dfs(v);
45 temp+=num[v];
46 }
47 num[u]=temp;
48 dp[u][1]=val[u];
49 dfs1(u,0,1,dp[u][1]);
50 return ;
51 }
52 int main()
53 {
54 int i,a;
55 while(~scanf("%d%d",&n,&m),n+m)
56 {
57 for(i=0;i<=n;i++) f[i].clear();
58 val[0]=0;
59 for(i=1;i<=n;i++)
60 {
61 scanf("%d%d",&a,val+i);
62 f[a].push_back(i);
63 }
64 m++;
65 memset(dp,0,sizeof(dp));
66 memset(num,0,sizeof(num));
67 dfs(0);
68 printf("%d
",dp[0][m]);
69 }
70 return 0;
71 }
72 */
73 /*
74 上面代码没剪枝，傻逼了忘了可以用0-1背包优化。
75 */
76 #include <iostream>
77 #include <cstdio>
78 #include <cstring>
79 #include <vector>
80 using namespace std;
81
82 const int maxn=205;
83 int dp[maxn][maxn];
84 int val[maxn],n,m;
85 vector<int> f[maxn];
86 inline int max(int a,int b){return a>b?a:b;}
87
88 void dfs(int u,int sum)
89 {
90 dp[u][1]=val[u];
91 if(m<=1) return;
92 for(int i=0;i<f[u].size();i++)
93 {
94 int v=f[u][i];
95 dfs(v,sum-1);
96 for(int j=sum;j>=2;j--)
97 {
98 for(int k=1;k<j;k++)
99 dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[v][k]);
100 }
101 }
102 return ;
103 }
104 int main()
105 {
106 int i,a;
107 while(~scanf("%d%d",&n,&m),n+m)
108 {
109 for(i=0;i<=n;i++) f[i].clear();
110 val[0]=0;
111 for(i=1;i<=n;i++)
112 {
113 scanf("%d%d",&a,val+i);
114 f[a].push_back(i);
115 }
116 m++;
117 memset(dp,0,sizeof(dp));
118 dfs(0,m);
119 printf("%d
",dp[0][m]);
120 }
121 return 0;
122 }
