#include<cstdio>

#include<cstring>

#include<iostream>

#define INF 999999999

using namespace std;

const int MAXN = ;

struct node

{

    int to;

    int v;

    int next;

}edge[MAXN*];

int pre[MAXN],n,index,vis[MAXN],m,num[MAXN];

int dp[MAXN][MAXN];

int max(int x,int y)

{

    return x>y?x:y;

}

void add(int x,int y,int z)

{

    edge[index].to = y;

    edge[index].v = z;

    edge[index].next = pre[x];

    pre[x] = index++;

}

void dfs(int root)

{

    int j,k;

    vis[root] = ;

    for(int i=pre[root]; i!=-; i=edge[i].next){

        int t = edge[i].to;

        if(!vis[t]){

            dfs(t);

            for(j=m+; j>=; j--){

                for(k=; k<j; k++){

                    dp[root][j] = max(dp[root][j], dp[root][k] + dp[t][j-k]);

                }

            }

        }

    }

}

int main()

{

    int i,j;

    while(~scanf("%d%d",&n,&m))

    {

        if(!n&&!m)break;

        index = ;

        memset(num,,sizeof(num));

        memset(pre,-,sizeof(pre));

        memset(dp,,sizeof(dp));

        memset(vis,,sizeof(vis));

        for(i=; i<=n; i++){

            int x, y;

            scanf("%d%d",&x,&y);

            num[x] ++;

            add(i, x, y);

            add(x, i, y);

            for(j=; j<=m; j++){

                dp[i][j] = y;

            }

        }

        dfs();

        printf("%d\n",dp[][m+]);

    }

}