#include "bits/stdc++.h"
// #include "grader.cpp"
#include "race.h"
using namespace std;
#define MAXN 300005
#define ll long long
#define f first
#define s second
const int inf = 2e5;
int ans = inf, dp[MAXN][101];
vector <pair<int,int>> E[MAXN];
void solve(int x,int p,int K) {
dp[x][0] = 0;
for(auto i : E[x]) {
if(i.f == p) continue;
solve(i.f, x, K);
for(int j = K; j >= 0; j--) {
if(j + i.s <= K) {
dp[x][j + i.s] = min(dp[x][j + i.s], dp[i.f][j] + 1);
}
}
}
}
void dfs(int x,int p, int K) {
vector<int> pd(K + 1, inf);
pd[0] = 0;
for(auto i : E[x]) {
if(i.f == p) continue;
dfs(i.f, x, K);
for(int j = K; j >= 0; j--) {
if(j + i.s <= K){
ans = min(ans, dp[i.f][K - j - i.s] + 1 + pd[j]);
}
}
for(int j = K; j >= 0; j--) {
if(j + i.s <= K)pd[j + i.s] = min(pd[j + i.s], dp[i.f][j] + 1);
}
}
}
int best_path(int N, int K, int H[][2], int L[]) {
for(int i = 0; i <= N; i++) {
for(int j = 0; j <= K; j++) {
dp[i][j] = inf;
}
}
for(int i = 0; i < N - 1; i++) {
E[H[i][0]].push_back({H[i][1], L[i]});
E[H[i][1]].push_back({H[i][0], L[i]});
}
solve(0, -1, K);
dfs(0, -1, K);
if(ans == inf) ans = -1;
return ans;
}
