// Make the best become better // No room for laziness #include<bits/stdc++.h> #define pb push_back #define fi first #define se second using namespace std; using ll = long long; using ld = long double; using ull = unsigned long long; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const int maxN = 2e5 + 5; const int maxM = 505; const int mod = 1e9 + 7; const ll oo = 1e18; int n, m; vector<int> adj[maxN]; int a[maxN]; int root; int f[maxN][maxM]; int sz[maxN]; int tmp[maxM]; void ReadInput() { cin >> n >> m; for(int i=1; i<=n; i++) { int p; cin >> p >> a[i]; if(!p) root = i; else { adj[p].pb(i); adj[i].pb(p); } } } void dfs(int u, int par) { // cout << u << " "; f[u][0] = 0; sz[u] = 1; for(int v : adj[u]) { if(v == par) continue; dfs(v, u); fill(tmp, tmp + m + 1, 0); for(int i=0; i<=min(m, sz[u]); i++) for(int j=0; j<=min(m - i, sz[v]); j++) tmp[i + j] = max(tmp[i + j], f[u][i] + f[v][j]); sz[u] += sz[v]; for(int i=1; i<=min(m, sz[u]); i++) f[u][i] = tmp[i]; } f[u][1] = max(f[u][1], a[u]); } void Solve() { dfs(root, 0); cout << f[root][m]; } int32_t main() { // freopen("x.inp", "r", stdin); ios_base::sync_with_stdio(false); cin.tie(nullptr); ReadInput(); Solve(); }