#include <bits/stdc++.h>
#include "race.h"
using ll =long long;
//#define int ll
ll LINF=1000000000000000000;
int INF=1e9;
#define pi pair<int,int>
#define pl pair<ll,ll>
#define endl '\n'
#define vi vector<int>
#define vii vector<vector<int>>
#define vl vector<ll>
#define vll vector<vector<ll>>
//#define int ll
using namespace std;
vector<vector<pi>>g;
int k;
int minimum=INF;
vi vinf={INF,-1};
int best_path(int N, int K, int H[][2], int L[])
{
g.resize(N);
k=K;
for(int i=0;i<N-1;i++){
g[H[i][0]].push_back(make_pair(H[i][1],L[i]));
g[H[i][1]].push_back(make_pair(H[i][0],L[i]));
}
vii dp(N,vi(k+1,INF));
for(int i=0;i<k+1;i++){
for(int j=0;j<N;j++){
for(pi child:g[j]){
if(child.second>i)continue;
dp[j][i]=min(dp[j][i],dp[child.first][i-child.second]+1);
}
}
}
for(int i=0;i<N;i++){
minimum=*std::min_element(dp[k].begin(), dp[k].end());
}
if(minimum==INF)return -1;
return minimum;
}
