#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define itn int
#define sz size()
#define pb push_back
#define pp pop_back()
#define ll long long
#define all(a) a.begin(),a.end()
#define ed "\n"
#define ff first
#define ss second
#define fio ios::sync_with_stdio(0); cin.tie(0);
const ll INF = (int)1e9;
const ll mod = (int)1e9 + 7;
vector<pair<int, int>> E[200009];
int dfs(int x, int par, int k){
if (k == 0)return 1;
int mn = -1;
for (auto i : E[x]){
if (i.ff != par && i.ss <= k){
int p = dfs(i.ff, x, k - i.ss);
if (p != -1)mn = (mn == -1 ? p + 1 : min(mn, p + 1));
}
}
return mn;
}
int best_path(int N, int K, int H[][2], int L[]){
for (int i = 0; i < N - 1; i ++){
E[H[i][0]].pb({H[i][1], L[i]});
E[H[i][1]].pb({H[i][0], L[i]});
}
int ans = 0;
for (int i = 0; i < N; i ++){
int p = dfs(i, -1, K);
if (p != -1)ans = (ans == 0 ? p : min(p, ans));
}
for (int i = 0; i < N; i ++)E[i].clear();
return ans - 1;
}
