#include<iostream> #include<vector> #include<set> #include<map> #include<unordered_map> #include<algorithm> #include<bitset> #include<queue> #include<numeric> #include<climits> #include<cstring> #include<cmath> #include<cstdlib> #include<cstdint> #include<algorithm> #define int long long using namespace std; const int N=2e5+5,M=505; int n,m; vector<int>child[N]; int p[N]; int v[N]; vector<int> dp[N]; int sz[N]; int find(int node,int past) { sz[node]=1; for(int i:child[node]) { sz[node]+=find(i,node); } return sz[node]; } void goodboy(int node,int past) { dp[node].resize(min(m,sz[node])+1); for(int i=0;i<dp[node].size();i++) { dp[node][i]=-1e18; } dp[node][0]=0; for(int i:child[node]) { goodboy(i,node); } int x=0; for(int i:child[node]) { for(int j=x;j>=0;j--) { for(int k=0;k<dp[i].size();k++) { if(j+k>m) { continue; } dp[node][j+k]=max(dp[node][j+k],dp[node][j]+dp[i][k]); } } x+=dp[i].size()-1; int r=dp[node].size(); x=min(r-1,x); } dp[node][1]=max(dp[node][1],v[node]); //cout<<node<<' '<<dp[node].back()<<' '<<dp[node].size()<<' '<<sz[node]<<' '<<'\n'; } void solve() { cin>>n>>m; int root; for(int i=1;i<=n;i++) { cin>>p[i]>>v[i]; if(p[i]==0) { root=i; } child[p[i]].push_back(i); } find(root,0); goodboy(root,0); if(dp[root][m]<0) { cout<<0; return; } cout<<dp[root][m]<<'\n'; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t=1; while(t--) { //cin>>t; solve(); } }