#include "race.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
using pr = pair<int, int>;
const int INF = 1e9+7, MOD = 1e9+7;
int n, k;
vector<vector<pr>> edge;
vector<map<int, int>> dp; // node, [sum of distance, {+ -}]
int ans;
void dfs(int node, int par) {
dp[node][0] = 0;
for (auto [next, d] : edge[node]) {
if (next == par) continue;
dfs(next, node);
for (auto [i, cnt] : dp[next]) {
long long dist = (long long)i + d;
if (dist > k) continue;
int need = k - (int)dist;
if (dp[node].count(need)) {
ans = min(ans, cnt + 1 + dp[node][need]);
}
}
for (auto [i, cnt] : dp[next]) {
long long dist = (long long)i + d;
if (dist > k) continue;
if (!dp[node].count((int)dist) || dp[node][(int)dist] > cnt + 1) {
dp[node][(int)dist] = cnt + 1;
}
}
}
}
int best_path(int N, int K, int h[][2], int l[]) {
n = N; k = K;
ans = INF;
edge.assign(n, vector<pr>());
dp.assign(n, map<int,int>());
for (int i = 0; i < n-1; i++) {
edge[h[i][0]].pb({h[i][1], l[i]});
edge[h[i][1]].pb({h[i][0], l[i]});
}
dfs(0, -1);
return ans == INF ? -1 : ans;
}
