#include "bits/stdc++.h"
#include "race.h"
using namespace std;
using ll = long long;
using vi = vector<ll>;
using pi = pair<ll, ll>;
const int mxN = 2e5 + 5;
const ll inf = 1e15;
ll dp[mxN][105];
ll dp2[mxN][105];
vector<pi> adj[mxN];
ll ans = inf;
void dfs(int x, int p, int K) {
fill(dp[x], dp[x] + 105, inf);
fill(dp2[x], dp2[x] + 105, inf);
dp[x][0] = 0;
for(auto [y, w] : adj[x]) {
if(y == p) continue;
dfs(y, x, K);
for(int j = 1; j <= K; ++j) {
if(j - w < 0) continue;
ll curr = dp[y][j - w] + 1;
if(dp[x][j] > curr) {
dp2[x][j] = dp[x][j];
dp[x][j] = curr;
} else if(dp2[x][j] > curr) {
dp2[x][j] = curr;
}
}
}
}
void solve(int x, int p, int K) {
ans = min(ans, dp[x][K]);
for(auto [y, w] : adj[x]) {
if(y == p) continue;
for(int j = 1; j <= K - 1; ++j) {
if(j - w < 0) continue;
ll one = dp[y][j - w] + 1;
ll two = dp[x][K - j];
if(K - j - w >= 0 && dp[y][K - j - w] + 1 == two)
two = dp2[x][K - j];
ans = min(ans, one + two);
}
solve(y, x, K);
}
}
int best_path(int N, int K, int H[][2], int L[])
{
for(int i = 0; i < N - 1; ++i) {
adj[H[i][0]].emplace_back(H[i][1], L[i]);
adj[H[i][1]].emplace_back(H[i][0], L[i]);
}
dfs(0, -1, K);
solve(0, -1, K);
return (ans == inf ? -1 : ans);
}
