#include <bits/stdc++.h> #define fastInp ios_base::sync_with_stdio(0); cin.tie(0); #define fr first #define sc second #define pii pair<int, int> #define pb push_back #define all(s) s.begin(), s.end() #define szof(s) (int)s.size() using namespace std; const int MAXN = (int)2e5 + 5; const int MAXM = (int)500 + 2; vector <int> g[MAXN]; int cost[MAXN]; int dp[MAXN][MAXM]; int tin[MAXN], tout[MAXN], tiktak = 0; int n, m; int root = -1; vector <int> sub[MAXN]; int DP[505][2]; void calc(int v) { memset(DP, -1, sizeof(DP)); DP[0][0] = 0; int tp = 0; for (int to : sub[v]) { for (int i = 0; i <= m; i++) { DP[i][tp ^ 1] = DP[i][tp]; } for (int cur = 1; cur <= m; cur++) { if (dp[to][cur] != -1) { for (int i = m; i >= 0; i--) { if (DP[i][tp] != -1 && i + cur <= m) { DP[i + cur][tp ^ 1] = max(DP[i + cur][tp ^ 1], DP[i][tp] + dp[to][cur]); } } } } tp ^= 1; } } void dfs(int v, int par) { if (v != root && szof(g[v]) == 1) { // leaf dp[v][1] = cost[v]; return; } for (int to : g[v]) { if (to != par) { dfs(to, v); sub[v].pb(to); } } dp[v][1] = max(dp[v][1], cost[v]); for (int to : sub[v]) { dp[v][1] = max(dp[v][1], dp[to][1]); } calc(v); for (int k = 2; k <= m; k++) { dp[v][k] = max(DP[k][0], DP[k][1]); } sub[v].clear(); } bool father(int a, int b) { return (tin[a] <= tin[b] && tout[b] <= tout[a]); } signed main() { fastInp; cin >> n >> m; memset(dp, -1, sizeof(dp)); for (int i = 1; i <= n; i++) { int par, x; cin >> par >> x; if (!par) { root = i; } else { g[par].pb(i); g[i].pb(par); } cost[i] = x; } dfs(root, -1); cout << max(0, dp[root][m]); }