#include <cstdio>#include <cmath>#include <algorithm>#include <cstring>#include <cstdlib>using namespace std;const int maxn=205;const int INF=0x7ffffff;struct Edge{    int to,dis,pre;    Edge(int to=0,int dis=0,int pre=0):to(to),dis(dis),pre(pre){}};int n,m;Edge edge[maxn];int head[maxn],pos;int dp[maxn][maxn];int money[maxn];void inint(){    memset(dp,0,sizeof(dp));    memset(head,-1,sizeof(head));    pos=0;}void add_edge(int s,int to,int dis){    edge[pos]=Edge(to,dis,head[s]);    head[s]=pos++;}int dfs(int s){    int ans,key;    ans=1,dp[s][1]=money[s];    for(int w=head[s];~w;w=edge[w].pre)    {        Edge &tmp=edge[w];        key=dfs(tmp.to);        ans+=key;        for(int i=ans;i>=1;i--)            for(int j=1;j<=key&&(j<i);j++)                dp[s][i]=max(dp[s][i],dp[s][i-j]+dp[tmp.to][j]);    }    return ans;}int main(){    int a;    while(~scanf("%d%d",&n,&m))    {        if(n==0&&m==0)break;        inint();        for(int i=1;i<=n;i++)        {            scanf("%d%d",&a,&money[i]);            add_edge(a,i,1);        }        dfs(0);        printf("%d\n",dp[0][m+1]);    }    return 0;}