#include <bits/stdc++.h>
#include "race.h"
using namespace std;
#define MAXN 200005
#define pb push_back
#define fi first
#define se second
typedef long long int lo;
lo k;
vector<pair<lo,lo> > v[MAXN];
lo vis[MAXN];
lo sub[MAXN];
lo mpp[1000005];
lo ans;
void dfs(lo node, lo par)
{
sub[node] = 1;
for(auto e: v[node]){
if(e.fi == par or vis[e.fi])
continue;
dfs(e.fi,node);
sub[node] += sub[e.fi];
}
}
lo centroid(lo node, lo par, lo val){
for(auto e: v[node]){
if(e.fi == par or vis[e.fi])
continue;
if(sub[e.fi] >= val/2)
return centroid(e.fi,node,val);
}
return node;
}
void check(lo node, lo par, lo cost,lo num){
if(cost > k)
return;
if(mpp[k-cost] != -1)
ans = min(ans, mpp[k-cost] + num);
for(auto e: v[node]){
if(e.fi == par or vis[e.fi])
continue;
check(e.fi,node,cost+e.se,num+1);
}
}
void build(lo node, lo par, lo cost,lo num){
if(cost > k)
return;
if(mpp[cost] == -1)
mpp[cost] = num;
else
mpp[cost] = min(num,mpp[cost]);
for(auto e: v[node]){
if(e.fi == par or vis[e.fi])
continue;
build(e.fi,node,cost+e.se,num+1);
}
}
void sifirla(lo node, lo par, lo cost){
if(cost > k)
return;
mpp[cost] = -1;
for(auto e:v[node]){
if(e.fi == par || vis[e.fi])continue;
sifirla(e.fi,node,cost+e.se);
}
}
void solve(lo node)
{
dfs(node,-1);
lo c = centroid(node,-1,sub[node]);
mpp[0] = 0;
for(auto e: v[c]){
if(vis[e.fi])
continue;
check(e.fi,c,e.se,1);
build(e.fi,c,e.se,1);
}
for(auto e: v[c]){
if(vis[e.fi])
continue;
sifirla(e.fi,c,e.se);
}
vis[c]=1;
for(auto e: v[c]){
if(vis[e.fi])
continue;
solve(e.fi);
}
}
int best_path(int N, int K, int H[][2], int L[])
{
k = K;
memset(mpp,-1,sizeof(mpp));
for (int i = 0; i < N-1; ++i)
{
v[H[i][0]].pb({H[i][1],L[i]});
v[H[i][1]].pb({H[i][0],L[i]});
}
ans = N+5;
solve(0);
if(ans == N+5)
ans = -1;
return ans;
}
