#include "bits/stdc++.h"
// #include "grader.cpp"
#include "race.h"
using namespace std;
#define MAXN 500005
#define ll long long
#define f first
#define s second
vector <pair<int,int>> E[MAXN];
int ans = -1;
void solve(int x,int p,int K,int nm) {
if(!K) {
if(!~ans) ans = nm;
ans = min(ans,nm);
}
for(auto i : E[x]) {
if(i.f == p) continue;
if(K >= i.s) solve(i.f, x, K - i.s, nm + 1);
}
}
int best_path(int N, int K, int H[][2], int L[]) {
for(int i = 0; i < N - 1; i++) {
E[H[i][0]].push_back({H[i][1], L[i]});
E[H[i][1]].push_back({H[i][0], L[i]});
}
for(int i = 0; i < N; i++) {
solve(i, 0, K, 0);
}
return ans;
}
