#include "race.h"
#include <bits/stdc++.h>
using namespace std;
struct mset{
set<pair<int64_t,int32_t>> st;
int xbias=0,ybias=0;
inline int size(){
return st.size();
}
inline int search(int x){
auto it=st.lower_bound({x-xbias,-2147483647});
if(it!=st.end() && (*it).first==x-xbias){
return (*it).second+ybias;
}
return -2147483648;
}
inline void insert(int x,int y){
st.insert({x-xbias,y-ybias});
}
};
inline void swap(mset& a,mset& b){
swap(a.st,b.st);
swap(a.xbias,b.xbias);
swap(a.ybias,b.ybias);
}
int n,k,ans=2147483647;
vector<vector<pair<int,int>>> adj;
vector<mset> st;
inline void dfs(int node,int p){
// cerr<<"dfs: "<<node<<" "<<p<<endl;
for(auto [i,w]:adj[node]){
if(i==p)continue;
dfs(i,node);
// cerr<<"merging "<<i<<" >to> "<<node<<endl;
st[i].xbias+=w;
st[i].ybias++;
if(st[i].size()>st[node].size()){
swap(st[i],st[node]);
}
auto it=st[i].st.begin();
for(;it!=st[i].st.end();it++){
int t=st[node].search(k - ((*it).first+st[i].xbias));
if(t!=-2147483648){
// cerr<<"ans"<<endl;
ans=min(ans,t+((*it).second)+st[i].ybias);
}
}
it=st[i].st.begin();
for(;it!=st[i].st.end();it=st[i].st.erase(it)){
st[node].insert((*it).first+st[i].xbias,(*it).second+st[i].ybias);
}
}
st[node].insert(0,0);
// cerr<<"st["<<node<<"]: ";for(auto [a,b]:st[node].st)cerr<<"("<<a+st[node].xbias<<","<<b+st[node].ybias<<") ";cerr<<endl;
int t=st[node].search(k);
if(t!=-2147483648){
// cerr<<"ass"<<endl;
ans=min(ans,t);
}
}
int best_path(int N, int K, int H[][2], int L[]){
n=N;
k=K;
st.resize(n);
adj.resize(n);
for(int i=0;i<n-1;i++){
adj[H[i][0]].push_back({H[i][1],L[i]});
adj[H[i][1]].push_back({H[i][0],L[i]});
}
dfs(0,-1);
return ans==2147483647?-1:ans;
}
