#include"bits/stdc++.h"
using namespace std;
#define ll long long
#define co cout<<
// stuff
const int maxn=1e4+5,maxm=101;
ll n,m;
vector<ll>v[maxn];
int arr[maxn];
ll root=-1;
int values[maxn][maxm];
void dfs(ll x,ll last){
vector<array<ll,3>>added;
for(auto i:v[x]){
if(i==last) continue;
dfs(i,x);
for(int j=1;j<=m;j++) added.push_back({i,values[i][j],j});
}
vector<pair<ll,ll>>apply;
ll lastt=-1;
for(auto[idx,val,wei]:added){
if(idx!=lastt){
lastt=idx;
for(auto [id,what]:apply) values[x][id]=max(values[x][id],(int)what);
apply.clear();
}
for(int i=m-wei;i>=0;i--){
if((values[x][i]||i==0)&&values[x][i+wei]<values[x][i]+val) apply.push_back({i+wei,values[x][i]+val});
}
}
for(auto [id,what]:apply) values[x][id]=max(values[x][id],(int)what);
values[x][1]=max(values[x][1],arr[x]);
}
void solve(){
cin>>n>>m;
for(int i=1;i<=n;i++){
ll a;
cin>>a>>arr[i];
if(a==0){
root=i;
continue;
}
v[i].push_back(a);
v[a].push_back(i);
}
dfs(root,-1);
co values[root][3];
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int _=1;
// cin>>_;
while(_--) solve();
}
