#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define pll pair <ll, ll>
const ll N =2 * 1e5 + 100;
vector <pll> q[N];
int k, ans = INT_MAX;
void dfs(int v, int pred, int sum, int cnt){
if(sum > k) return;
if(sum == k){
ans = min(ans, cnt);
return;
}
for(auto u : q[v]){
if(u.F == pred) continue;
dfs(u.F, v, sum + u.S, cnt + 1);
}
}
int best_path(int n, int gk, int h[][2], int l[]){
k = gk;
for(int i = 0; i < n - 1; i++){
q[h[i][0]].pb({h[i][1], l[i]});
q[h[i][1]].pb({h[i][0], l[i]});
}
for(int i = 1; i <= n; i++){
dfs(i, -1, 0, 0);
}
if(ans == INT_MAX) return -1;
return ans;
}
// int main(){
// vector <int> s;
// int n;
// cin >> n;
// for(int i = 0, x; i < n; i++){
// cin >> x;
// s.pb(x);
// }
// return 0;
// }
