#include<bits/stdc++.h>
#include "race.h"
#define INF 987654321
using namespace std;
vector<int>cg[200005],cv[200005];
stack<int>used;
int ch[200005],p[1000005],n,cn,k,ans=INF;
bool col[200005];
void count_num(int idx,int prev) {
int i; cn++;
for(i=0;i<cg[idx].size();i++) {
if(!col[cg[idx][i]] && cg[idx][i]!=prev) {
count_num(cg[idx][i],idx);
}
}
}
pair<int,int> find_cen(int idx,int prev) {
pair<int,int> ret(INF,-1),tmp;
int i,cc=1,mc=0;
for(i=0;i<cg[idx].size();i++) {
if(col[cg[idx][i]] || cg[idx][i]==prev) continue;
tmp=find_cen(cg[idx][i],idx);
if(tmp.first<ret.first) ret=tmp;
mc=max(mc,ch[cg[idx][i]]);
cc+=ch[cg[idx][i]];
}
mc=max(mc,cn-cc);
if(mc<ret.first) ret={mc,idx};
ch[idx]=cc;
return ret;
}
void match(int idx,int prev,int cnt,int len) {
if(len>k) return;
int i; ans=min(ans,p[k-len]+cnt);
for(i=0;i<cg[idx].size();i++) {
if(!col[cg[idx][i]] && cg[idx][i]!=prev) {
match(cg[idx][i],idx,cnt+1,len+cv[idx][i]);
}
}
}
void apply(int idx,int prev,int cnt,int len) {
if(len>k) return;
int i; p[len]=min(p[len],cnt); used.push(len);
for(i=0;i<cg[idx].size();i++) {
if(!col[cg[idx][i]] && cg[idx][i]!=prev) {
apply(cg[idx][i],idx,cnt+1,len+cv[idx][i]);
}
}
}
void dnc(int idx) {
while(!used.empty()) {p[used.top()]=INF; used.pop();}
p[0]=0;
cn=0; count_num(idx,-1);
int i,cen=find_cen(idx,-1).second;
for(i=0;i<cg[cen].size();i++) {
if(col[cg[cen][i]])continue;
match(cg[cen][i],cen,1,cv[cen][i]);
apply(cg[cen][i],cen,1,cv[cen][i]);
}
col[cen]=1;
for(i=0;i<cg[cen].size();i++) {
if(!col[cg[cen][i]]) {
dnc(cg[cen][i]);
}
}
}
int best_path(int N, int K, int H[][2], int L[])
{
int i; n=N; k=K;
for(i=0;i<n-1;i++) {
cg[H[i][0]].push_back(H[i][1]);
cv[H[i][0]].push_back(L[i]);
cg[H[i][1]].push_back(H[i][0]);
cv[H[i][1]].push_back(L[i]);
}
for(i=1;i<=k;i++)p[i]=INF;
dnc(0);
return (ans==INF?-1:ans);
}
