#include "race.h"
#include<bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define pq priority_queue
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define eb emplace_back
#define F first
#define S second
using namespace std;
vector<pair<int, int>> adj[200001];
int mn = 2e9;
void dfs(int s, int val, int cnt, int key, int vis[]) {
if (val == key) {mn = min(mn, cnt); return ;}
for (auto i: adj[s]) {
if (vis[i.F] || val + i.S > key) continue ;
vis[i.F] = 1; dfs(i.F, val + i.S, cnt + 1, key, vis); vis[i.F] = 0;
}
}
int best_path(int N, int K, int H[][2], int L[]) {
for (int i = 0; i < N-1; i++) {
adj[H[i][0]].pb({H[i][1], L[i]});
adj[H[i][1]].pb({H[i][0], L[i]});
}
int a[N] = {0};
for (int i = 0; i < N; i++) dfs(i, 0, 0, K, a);
return mn;
}
