#include<bits/stdc++.h>
#define N 1005
using namespace std;
struct node{
	int data;
	int son,bro;
}tree[1005];
int f[N][N];
int n,m,cnt;
int a[1005];
inline void add(int x,int y);
int dfs(int x,int k);
int main()
{
	memset(f,-1,sizeof(f));
	cin>>n>>m;
	m++;
	for(int i=1;i<=n;i++)
	{
		int k;
		scanf("%d%d",&k,&a[i]);
		add(k,i);
	}
//	for(int i=0;i<=n;i++)
//	{
//		build(i);
//	}
//	for(int i=0;i<=n;i++)
//	{
//		printf("%d %d\n",tree[i].l,tree[i].r);
//	}
	printf("%d\n",dfs(0,m));
	return 0;
}
inline void add(int x,int y)
{
	tree[y].bro=tree[x].son;
	tree[x].son=y;
}
int dfs(int x,int k)
{
	if(f[x][k]!=-1) return f[x][k];
	if(k==0)
	{
		f[x][k]=0;
		return f[x][k];
	}
	f[x][k]=0;
	if(x==0)
	{
		f[x][k]=dfs(tree[x].son,k-1);
		return f[x][k];
	}
	else
	{
		f[x][k]=dfs(tree[x].bro,k);
		for(int i=0;i<=k-1;i++)
		{
			f[x][k]=max(f[x][k],dfs(tree[x].son,i)+dfs(tree[x].bro,k-1-i)+a[x]);
		}
	}
	return f[x][k];
}