#include <bits/stdc++.h>
#include "race.h"
using namespace std;
int k, n;
vector<pair<int, int>> g[200005];
int rez=1e9;
int dp[200005][105];
void f(int u, int priv)
{
for(int i =0; i <= k; i++) dp[u][i]=1e9;
dp[u][0]=0;
for(auto i: g[u])
{
if(i.first == priv) continue;
f(i.first, u);
for(int j = 0; j <= k-i.second; j++)
{
rez = min(rez, dp[i.first][k-j-i.second]+1+dp[u][j]);
}
for(int j = i.second; j <= k; j++)
{
dp[u][j] = min(dp[u][j], dp[i.first][j - i.second]+1);
}
}
}
int best_path(int N, int K, int H[][2], int L[])
{
n = N;
k = K;
for(int i =0; i < n-1; i++)
{
g[H[i][0]].push_back({H[i][1], L[i]});
g[H[i][1]].push_back({H[i][0], L[i]});
}
f(0, -1);
if(rez==1e9) return -1;
return rez;
}
