#include<bits/stdc++.h>
using namespace std;
const int N=3e3+5;
vector<int>g[N];
int n,m,mem[N][N],a[N];
int dfs(int u,int v){
	if(mem[u][v]!=-1){
		return mem[u][v];
	}
	if(!v){
		return 0;
	}
	int dp[N]={};
	for(int i:g[u]){
		for(int j=0;j<v;j++){
			for(int k=v-1;k>=j;k--){
				dp[k]=max(dp[k],dp[k-j]+dfs(i,j));
			}
		}
	}
	return mem[u][v]=dp[v-1]+a[u];
}
int main(){
	cin>>n>>m;
	for(int i=1,f;i<=n;i++){
		cin>>f>>a[i],g[f].push_back(i);
	}
	memset(mem,-1,sizeof(mem));
	cout<<dfs(0,m+1);
}