#include<bits/stdc++.h>
using namespace std;
const int N = 2E5 + 1 , M = 1E6 + 1;
vector<int> dead(N) , sz(N) , f(M , -1);
vector<pair<int , int>> g[N];
int gsz(int u , int p = 0){
int s = 0;
for(auto [v , w] : g[u]){
if(v != p && !dead[v]){
s += gsz(v , u);
}
}
sz[u] = ++s;
return sz[u];
}
int find(int u , int m , int p = 0){
for(auto [v , w] : g[u]){
if(v != p && !dead[v] && sz[v] > m / 2){
return find(v , m , u);
}
}
return u;
}
void calc(int u , int p , int D , int L , int K , vector<pair<int , int>> &d){
if(L > K){
return;
}
d.emplace_back(L , D);
++D;
for(auto [v , w] : g[u]){
if(v != p && !dead[v]){
calc(v , u , D , L + w , K , d);
}
}
}
int solve(int u , int k){
u = find(u , gsz(u));
int ans = 1E9;
f[0] = 0;
vector<int> clr;
for(auto [v , w] : g[u]){
if(!dead[v]){
vector<pair<int , int>> dists;
calc(v , u , 1 , w , k , dists);
for(auto [X , Y] : dists){
if(f[k - X] != -1){
ans = min(ans , Y + f[k - X]);
}
}
for(auto [X , Y] : dists){
if(f[X] == -1){
f[X] = Y;
}else{
f[X] = min(f[X] , Y);
}
clr.emplace_back(X);
}
}
}
for(int x : clr){
f[x] = -1;
}
dead[u] = 1;
for(auto [v , w] : g[u]){
if(!dead[v]){
ans = min(ans , solve(v , k));
}
}
return ans;
}
int best_path(int N, int K, int H[][2], int L[]){
for(int i = 0;i < N - 1;i ++){
for(int w = 0;w < 2;w ++){
++H[i][w];
}
for(int w = 0;w < 2;w ++){
g[H[i][w]].emplace_back(H[i][w ^ 1] , L[i]);
}
}
int A = solve(1 , K);
if(A > N){
A = -1;
}
return A;
}
