#include<iostream> // #include<bits/stdc++.h> #include<algorithm> #include<set> #include<map> #include<vector> #include<queue> #define pb push_back #define ll long long #define all(v) (v).begin() , (v).end() using namespace std; const int N = 2e5+1 , inf = 1e9; int dp[N][502][2] ; int x[N] , n , k ; int tin[N] , tout[N] , timer = 0 ; pair<int ,int >q[N]; vector<int>g[N]; void dfs(int v , int p ){ tin[v] = ++timer; for(auto it:g[v]){ dfs(it , v); } tout[v] = ++timer; q[timer] = {x[v] , tin[v]}; } signed main(){ // freopen("d.in" , "r" , stdin); // freopen("d.out" , "w" , stdout); ios_base::sync_with_stdio(0) , cin.tie(0); cin >> n >> k; int pr =0 ; for(int i= 1; i <= n ; i++){ int p; cin >> p >> x[i]; if(p == 0 )pr =i ; g[p].pb(i); } for(int i= 0 ; i <= n; i++){ for(int j =0 ; j<= k ; j++)dp[i][j][0] = -inf; } for(int i = 1 ; i <= n ; i++){ dp[i][0][0] = 0 ; } dfs(pr , 0 ); for(int i=1 ; i <= timer; i++){ for(int j = 1; j <= k ; j++){ dp[i][j][1] = dp[i-1][j][0]; int l = q[i].second , val = q[i].first; if(l==0)continue; dp[i][j][1] = max(dp[i][j][1] , dp[l-1][j-1][0]+val); // cout << i<< ' ' << j << ' ' << dp[i][j] << '\n'; } for(int j = 1; j <= k ; j++){ dp[i][j][0] = dp[i][j][1]; dp[i][j][1] =-inf ; } // cout << i << ' ' << dp[i] << '\n'; } cout << dp[timer][k][0]; }