1 #include <cstdio>
 2 #include <cstring>
 3 #define max(x,y) (x >= y ? x : y)
 4 #define MAX 202
 5 using namespace std;
 6 
 7 int ver[MAX][MAX];
 8 int dp[MAX][MAX];
 9 int count[MAX];
10 int v[MAX];
11 int n,m;
12 
13 void reset(){
14     memset(ver,0,sizeof(ver));
15     memset(dp,0,sizeof(dp));
16     memset(count,0,sizeof(count));
17     memset(v,0,sizeof(v));
18 }
19 
20 void dfs(int r){
21     for(int i=0;i<count[r];i++){
22         dfs(ver[r][i]);
23     }
24     dp[r][1]=v[r];
25     for(int i=0;i<count[r];i++){
26         int t=ver[r][i];
27         for(int j=m;j>1;j--){
28             for(int k=1;k<j;k++){
29                 /** k不能等于j，因为k==j的意思就是以r为子树的树上取除去根节点以外的节点一共j个，但是因为如果不去r的话，就无法取它的孩子，所以k!=j **/
30                 dp[r][j]=max(dp[r][j],dp[r][j-k]+dp[t][k]);
31             }
32         }
33     }
34 }
35 
36 int main()
37 {
38     //freopen("data.txt","r",stdin);
39     while(scanf("%d %d",&n,&m),(n+m)){
40         reset();
41         for(int i=1;i<=n;i++){
42             int a;
43             scanf("%d",&a);
44             scanf("%d",&v[i]);
45             ver[a][count[a]]=i;
46             count[a]++;
47         }
48         m++;
49         dfs(0);
50         printf("%d\n",dp[0][m]);
51     }
52     return 0;
53 }