#include <bits/stdc++.h>
using namespace std;
int n,k,l;
bool jo;
long long kappa;
struct munk{vector<int>kim; long long fon;};
vector<munk>a;
void tav(int x, long long maxh){
    long long d=0;
    for(int i:a[x].kim){
        tav(i,maxh);
        d=max(d, kappa+a[i].fon);}
    if(d+a[x].fon>maxh){
        l++; kappa=-a[x].fon;}
    else kappa=d;
    if(l>k){jo=0; return;}
    }

int main()
{
    //ifstream f("szamok.txt");
    cin>>n>>k; a.resize(n+1);
    vector<bool>b(n+1);
    for(int i=2; i<=n; i++){
        long long x,y; cin>>x>>y;
        a[x].kim.push_back(i);
        a[i].fon=y;}
    long long s=0,t=10e14,koz;
    while(s!=t){
        jo=1;
        l=0; koz=(s+t)/2;
        tav(1,koz);
        if(jo)t=koz;
        else s=koz+1;}
    cout<<t;
    return 0;
}