#include <bits/stdc++.h>
using namespace std;
#define loop(i, a, b) for(int i = a; i <= b; i++)
vector<vector<int>> graph;
vector<vector<int>> dp;
vector<int> arr, tin, tout;
int curr_preorder = (-1);
void prep(int v) {
tin[v] = ++curr_preorder;
for(int s : graph[v]) {
prep(s);
}
tout[v] = curr_preorder;
}
int n, m;
void solve(int v) {
dp[tin[v]][0] = 0;
dp[tin[v] + 1][m] = max(dp[tin[v] + 1][m], dp[tin[v]][m]);
loop(i, 0, m-1) {
dp[tout[v] + 1][i + 1] = max(dp[tout[v] + 1][i + 1], dp[tin[v]][i] + arr[v]);
dp[tin[v] + 1][i] = max(dp[tin[v] + 1][i], dp[tin[v]][i]);
}
for(int s : graph[v]) {
solve(s);
}
}
int main() {
cin.tie(0)->sync_with_stdio(false);
cin >> n >> m;
dp.resize(n + 1, vector<int>(m + 1, (-1e9)));
graph.resize(n + 1);
tout.resize(n + 1);
tin.resize(n + 1);
arr.resize(n + 1);
int root;
loop(i, 1, n) {
int p; cin >> p >> arr[i];
if(p == 0) root = i;
else graph[p].push_back(i);
}
prep(root);
solve(root);
cout << dp[n][m] << '\n';
}
