Const maxn=10000;
Type number=0..300000;
Var
key,s,a:array[1..maxn]of number;
f,g:array[1..maxn]of boolean;
e,son:array[1..maxn,0..300]of number;
n,k,root,w,t:number;
procedure init;
var i,x,y:number;
d:array[1..maxn]of number;
begin
fillchar(d,sizeof(d),0);
readln(n,k,key[1]);
for i:=2 to n do
begin
readln(x,y);
inc(d[x]);inc(e[x,0]);e[x,e[x,0]]:=i;
inc(d[i]);inc(e[i,0]);e[i,e[i,0]]:=x;
key[i]:=y;
end;
for i:=1 to n do
if d[i]=1 then
begin root:=i;break;end;
end;
procedure build(i:number);
var j:number;
begin
f[i]:=true;
for j:=1 to e[i,0] do
if not f[e[i,j]] then
begin
inc(son[i,0]);
son[i,son[i,0]]:=e[i,j];
build(e[i,j]);
end;
end;
function check(i:number):number;
var j,sum:number;
begin
sum:=0;
for j:=1 to son[i,0] do
inc(sum,check(son[i,j]));
inc(sum,key[i]);
if sum>=w then
begin
inc(t); a[t]:=i;
inc(s[i]); sum:=0;
end;
check:=sum;
end;
procedure work1;
var i,sum:number;
begin
sum:=0;for i:=1 to n do inc(sum,key[i]);
w:=sum div (k-1); t:=0;
sum:=check(root);
dec(s[a[t]]);dec(t);
end;
function cal(i:number):number;
var j,sum:number;
begin
sum:=key[i];
for j:=1 to son[i,0] do
if s[son[i,j]]=0 then
inc(sum,cal(son[i,j]));
exit(sum);
end;
procedure work2;
var i,j,w1,w2,temp,l1,l2:number;
begin
for i:=t+1 to k-1 do
begin
inc(s[son[root,1]]);
a[i]:=son[root,1];
end;
while true do
begin
fillchar(g,sizeof(g),false);
w1:=cal(root);
g[root]:=true;
for i:=1 to k-1 do
if g[a[i]] then w1:=0
else begin
temp:=cal(a[i]);
g[a[i]]:=true;
if w1>temp then w1:=temp;
end;
w2:=0;
for i:=1 to k-1 do
for j:=1 to son[a[i],0] do
if s[son[a[i],j]]=0 then
begin
temp:=cal(son[a[i],j]);
if temp>w2 then
begin
w2:=temp;
l1:=i;l2:=j;
end;
end;
if w1<=w2 then
begin
dec(s[a[l1]]);
inc(s[son[a[l1],l2]]);
a[l1]:=son[a[l1],l2];
end
else break;
end;
writeln(w1);
end;
Begin
fillchar(f,sizeof(f),false);
fillchar(e,sizeof(e),0);
fillchar(son,sizeof(son),0);
init;
build(root);
work1;
work2;
End.