#include<bits/stdc++.h>

using namespace std;

#define N 205

struct Edge{int to,nxt;}e[N<<];

int head[N],tot,n,m,a[N];

void init(){memset(head,-,sizeof head);tot=;}

void add(int u,int v){

    e[tot].to=v;e[tot].nxt=head[u];head[u]=tot++;

}

int dp[N][N];

void dfs(int u,int pre,int C){

    for(int i=head[u];i!=-;i=e[i].nxt){

        int v=e[i].to;

        if(v==pre)continue;

        for(int j=;j<=C-;j++)

            dp[v][j]=dp[u][j]+a[v];

        dfs(v,u,C-);

        for(int j=;j<=C;j++)

            dp[u][j]=max(dp[u][j],dp[v][j-]);

    }

}

int main(){

    while(cin>>n>>m && n){

        init();

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

            int fa;cin>>fa>>a[i];

            add(i,fa);add(fa,i);

        }

        memset(dp,,sizeof dp);

        dfs(,,m);

        int ans=;

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

            ans=max(ans,dp[][j]);

        cout<<ans<<endl;

    }

}