#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define ll long long #define int long long #define mod 1000000007 #define ld long double #define all(x) (x).begin() , (x).end() #define pb push_back using namespace __gnu_pbds; using namespace std; template <typename T> using ordered_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>; const ll maxn=200005,maxm=505; ll n,m; vector<vector<ll>> v(maxn); vector<vector<ll>> dp(maxn+2,vector<ll>(maxm+2,LLONG_MIN)); vector<ll> val(maxn); vector<ll> combine(vector<ll>& a,vector<ll>& b){ vector<ll> r(min((ll)(a.size()+b.size()-1),m+1),LLONG_MIN); for(int i=0; i<a.size(); i++){ // if(a[i]<0) continue; for(int j=0; j<b.size(); j++){ // if(b[i]<0) continue; if(i+j<=m) r[i+j]=max(r[i+j],a[i]+b[j]); } } return r; } void dfs(ll st,ll p){ dp[st]={0}; for(ll i:v[st]){ if(i==p) continue; dfs(i,st); dp[st]=combine(dp[st],dp[i]); } if(dp[st].size()>1) dp[st][1]=max(dp[st][1],val[st]); else dp[st].pb((val[st])); } signed main(){ cin.tie(0)->sync_with_stdio(0); ll tt=1; // cin >> tt; while(tt--){ // ll n,m; ll root; cin >> n >> m; // dp.assign(n+2,vector<ll>(m+2,LLONG_MIN)); for(int i=0; i<n; i++){ ll x,y; cin >> x >> y; if(x==0) root=i+1; v[x].pb(i+1),val[i+1]=y; } dfs(root,0); cout << dp[root][m]; } return 0; }