#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+]);
}
}