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