#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
int sz[200005], mins[1000005];
bool vis[200005];
vector<pair<int, int>> adj[200005];
int ans = 1e9, k;
int dfs(int u, int par){
if(vis[u]) return 0;
sz[u] = 1;
for(auto v: adj[u]){
if(v.fi != par){
sz[u] += dfs(v.fi, u);
}
}
return sz[u];
}
int ctr(int u, int par, int szz){
for(auto v: adj[u]){
if(v.fi == par) continue;
if(!vis[v.fi] && sz[v.fi] * 2 > szz){
return ctr(v.fi, u, szz);
}
}
return u;
}
void get_ans(int u, int par, int len, int dep){
if(len > k) return;
ans = min(ans, mins[k - len] + dep);
for(auto v: adj[u]){
if(!vis[v.fi] && v.fi != par){
get_ans(v.fi, u, len + v.se, dep + 1);
}
}
}
void dfs2(int u, int par, int len, int dep, int tp){
if(len > k) return;
if(tp) mins[len] = min(mins[len], dep);
else mins[len] = 1e9;
for(auto v: adj[u]){
if(!vis[v.fi] && v.fi != par){
dfs2(v.fi, u, len + v.se, dep + 1, tp);
}
}
}
void ctr_dcmp(int u){
int cntr = ctr(u, -1, dfs(u, -1));
for(auto v: adj[cntr]){
if(!vis[v.fi]){
get_ans(v.fi, cntr, v.se, 1);
dfs2(v.fi, cntr, v.se, 1, 1);
}
}
for(auto v: adj[cntr]){
if(!vis[v.fi]){
dfs2(v.fi, cntr, v.se, 1, 0);
}
}
vis[cntr] = true;
for(auto v: adj[cntr]){
if(!vis[v.fi]){
ctr_dcmp(v.fi);
}
}
}
int best_path(int N, int K, int H[][2], int L[]){
k = K;
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]});
}
for(int i = 1; i <= K; i++) mins[i] = 1e9;
mins[0] = 0;
ctr_dcmp(0);
if(ans == 1e9) ans = -1;
return ans;
}
