#include <bits/stdc++.h>
#define NMAX 20002
#define MMAX 501
using namespace std;
int n, m, cnt=0;
int memorie[NMAX];
vector<int> fii[NMAX];
int nr_frunze[NMAX]; ///nr_frunze[i] = numarul de frunze al subarborelui lui i
int liniar[NMAX]; ///liniarizarea arborelui
int fin[NMAX]; ///fin[i] = pozitia unde se termina subarborele lui i
void dfs(int nod)
{
liniar[++cnt]=nod;
for(auto& fiu : fii[nod])
{
dfs(fiu);
}
fin[nod]=cnt+1;
}
int dp[NMAX][MMAX]; ///dp[i][j] = memoria maxima daca luam j cipuri din intervalul [i...n]
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
int radacina;
for(int i=1; i<=n; i++)
{
int tata;
cin >> tata >> memorie[i];
if(tata==0) radacina=i;
else fii[tata].push_back(i);
}
dfs(radacina); ///precalculam numarul de frunze al fiecarui subarbore si liniarizam arborele
for(int i=n; i>=1; i--)
{
nr_frunze[i]=1+nr_frunze[fin[liniar[i]]];
for(int j=1; j<=m && j<=nr_frunze[i]; j++)
{
dp[i][j]=memorie[liniar[i]]+dp[fin[liniar[i]]][j-1]; ///cazul in care luam nodul liniar[i]
}
for(int j=1; j<=m; j++) dp[i][j]=max(dp[i][j], dp[i+1][j]); ///maxime partiale pe dp
}
cout << dp[radacina][m];
return 0;
}
