#include "race.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
vector<pair<ll,ll>> adj[200005];
bool del[200005];
ll sub[200005];
ll dp[1000000];
ll k;
ll ans = 1e10;
inline ll get_sub(ll node, ll parent){
sub[node] = 1;
for(auto go : adj[node]){
if(go.first == parent or del[go.first]) continue;
sub[node] += get_sub(go.first,node);
}
return sub[node];
}
inline ll get_centroid(ll node, ll parent, ll tree_size){
for(auto go : adj[node]){
if(go.first == parent or del[go.first]) continue;
if(sub[go.first] >= tree_size/2) return get_centroid(go.first,node,tree_size);
}
return node;
}
inline void control(ll node, ll parent, ll val, ll edge){
if(val > k) return;
if(dp[k-val] != -1) ans = min(ans,dp[k-val] + edge);
for(auto go : adj[node]){
if(go.first == parent or del[go.first]) continue;
control(go.first,node,val+go.second,edge+1);
}
}
inline void build(ll node, ll parent, ll val, ll edge){
if(val > k) return;
if(dp[val] != -1) dp[val] = min(dp[val],edge);
else dp[val] = edge;
for(auto go : adj[node]){
if(go.first == parent or del[go.first]) continue;
build(go.first,node,val+go.second,edge+1);
}
}
inline void dp_reset(ll node, ll parent, ll val){
if(val > k) return;
dp[val] = -1;
for(auto go : adj[node]){
if(go.first == parent or del[go.first]) continue;
dp_reset(go.first,node,val+go.second);
}
}
inline void solve(ll node){
ll centroid = get_centroid(node,-1,get_sub(node,-1));
dp[0] = 0;
for(auto go : adj[centroid]){
if(del[go.first]) continue;
control(go.first,centroid,go.second,1);
build(go.first,centroid,go.second,1);
}
for(auto go : adj[centroid]){
if(del[go.first]) continue;
dp_reset(go.first,centroid,go.second);
}
del[centroid] = 1;
for(auto go : adj[centroid]){
if(del[go.first]) continue;
solve(go.first);
}
}
int best_path(int N, int K, int H[][2], int L[]){
k = K;
memset(dp,-1,sizeof(dp));
for(ll i = 0 ; i < N-1 ; i++){
adj[H[i][1]].pb({H[i][0],L[i]});
adj[H[i][0]].pb({H[i][1],L[i]});
}
solve(0);
if(ans == 1e10) ans = -1;
return ans;
}
