#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<vector>

using namespace std;

#define ll long long

const int maxn=2e2+;

const int INF=0x3f3f3f3f;

///dp[i][j] 表示以i为跟节点的树，选其中的j个节点可以达到的最大值

int dp[maxn][maxn];

vector<int>v[maxn];

int N,M,x,a[maxn];

void dfs(int n,int m)

{

    dp[n][]=a[n];

    int len=v[n].size();

    for(int i=; i<len; i++)  ///01背包第一层循环

    {

        if(m>) dfs(v[n][i],m-);

        for(int j=m-; j>=; j--)  ///第二层循环，相当于背包的重量，-1的原因是根节点必选

            for(int k=; k<=j; k++)  ///k是在第i棵树上选K个子节点

                dp[n][j+]=max(dp[n][j+],dp[n][j+-k]+dp[v[n][i]][k]);

    }

}

int main()

{

    //freopen("in.txt","r",stdin);

    while(scanf("%d%d",&N,&M) && N+M)

    {

        memset(dp,,sizeof(dp));

        memset(a,,sizeof(a));

        for(int i=; i<=N; i++) v[i].clear();

        for(int i=; i<=N; i++)

        {

            scanf("%d%d",&x,&a[i]);

            v[x].push_back(i);

        }

        dfs(,M+); ///0是补的根节点,M+1是可以取几个结点,因为多加了一个0结点 值为0 所以要M+1

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

    }

    return ;

}