#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define vll vector<pll>
#define vii vector<pii>
using namespace std;
vii G[500000];
bool dp[10000][10000];
int K;
void dfs(int at, int path, int passed_cities, int prev){
if(path > K)
return;
for(auto next : G[at]){
if(next.first == prev)
continue;
else{
dp[next.first][passed_cities] = path + next.second;
dfs(next.first, path + next.second, passed_cities + 1, at);
}
}
}
int best_path(int n, int k, int H[][2], int L[]){
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]));
}
dfs(0, 0, 0, -1);
int best = 1e9;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
best = min(best, j);
}
}
if(best == 1e9)
return -1;
return best;
}
