#include <bits/stdc++.h>
#include "race.h"
using namespace std;
const int maxn = 1e6 + 5;
const int inf = 1e9 + 7;
int depth[maxn];
int road[maxn];
int n, k;
vector<pair<int, int>> tr[maxn];
int dp[maxn][105];
int result = inf;
void solve(int u, int p){
for(auto node : tr[u]){
int v = node.first;
int w = node.second;
if(v == p) continue;
solve(v, u);
for(int in = 0; in + w <= k; in++){
int out = k - w - in;
//cout << "Before : " << result << " " << dp[u][out] << " " << dp[v][in] << endl;
result = min(result, dp[u][out] + dp[v][in] + 1);
//cout << "After : " << result << endl;
}
for(int j = 0; j + w <= k; j++){
dp[u][j + w] = min(dp[u][j + w], dp[v][j] + 1);
}
}
}
void dfs(int u, int p){
for(auto node : tr[u]){
int v = node.first;
int w = node.second;
if(v == p) continue;
depth[v] = depth[u] + 1;
road[v] = road[u] + w;
dfs(v, u);
}
}
int best_path(int N, int K, int H[][2], int L[]){
n = N;
k = K;
for(int i = 0; i < n - 1; i++){
int a, b, l;
a = H[i][0];
b = H[i][1];
l = L[i];
tr[a].push_back({b, l});
tr[b].push_back({a, l});
}
if(k <= 100){
for(int i = 0; i < n; i++){
dp[i][0] = 0;
}
for(int i = 0; i < n; i++){
for(int j = 1; j <= k; j++){
dp[i][j] = inf;
}
}
solve(0, -1);
}else{
for(int i = 0; i < n; i++){
depth[i] = 0;
road[i] = 0;
dfs(i, -1);
for(int j = 0; j < n; j++){
if(road[j] == k && result > depth[j]){
result = depth[j];
}
}
}
}
if(result == inf){
return -1;
}else{
return result;
}
}
