#include <bits/stdc++.h>
using namespace std;
#include "race.h"
#define pb push_back
struct edge
{
int node, weight;
};
int k, ans = 1e9;
vector<edge> g[1001];
map<int, int> dp[1001];
void dfs(int now, int par)
{
for(auto x : g[now])
{
if(x.node == now) continue ;
dfs(x.node, now);
}
for(auto x : g[now])
{
if(x.node == now) continue ;
for(auto it : dp[x.node])
{
int a = x.weight + it.first;
int b = k - a;
if(b <= 0) continue ;
if(dp[now].count(b)) ans = min(ans, dp[now][b] + it.second + 1);
}
for(auto it : dp[x.node])
{
int w = it.first + x.weight;
if(w > k) continue ;
else if(w == k) ans = min(ans, it.second + 1);
else if(dp[now].count(w)) dp[now][w] = min(dp[now][w], it.second + 1);
else dp[now][w] = it.second + 1;
}
}
dp[now][0] = 0;
}
int best_path(int N, int K, int H[][2], int L[])
{
k = K;
for(int i=0 ; i<N-1 ; i++)
{
int u = H[i][0] + 1, v = H[i][1] + 1, w = L[i];
g[u].pb({v, w}), g[v].pb({u, w});
}
dfs(1, 0);
if(ans == 1e9) ans = -1;
return ans;
}
