#include "race.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 200001;
const int K = 101;
vector<array<int, 2>> adj[N];
int dp[N][K];
int n, k;
void dfs1(int node, int parent)
{
dp[node][0] = 0;
for (auto next : adj[node])
{
if (next[0] == parent) continue;
dfs1(next[0], node);
for (int i = 0; i + next[1] <= k; i++)
{
//cout << node << " " << next[0] << " " << i << " " << dp[next[0]][i] << endl;
dp[node][i + next[1]] = min(dp[node][i + next[1]], dp[next[0]][i] + 1);
}
}
}
int best_path(int n1, int k1, int H[][2], int L[])
{
n = n1;
k = k1;
for (int i = 0; i < n; i++) for (int j = 0; j <= k; j++) dp[i][j] = N;
for (int i = 0; i < n; i++)
{
adj[H[i][0]].push_back({H[i][1], L[i]});
adj[H[i][1]].push_back({H[i][0], L[i]});
}
dfs1(0, -1);
int res = N;
for (int i = 0; i < n; i++)
{
vector<int> bestAt(k + 1, N);
bestAt[0] = 0;
for (auto next : adj[i])
{
for (int j = 0; j + next[1] <= k; j++)
{
res = min(res, dp[next[0]][j] + 1 + bestAt[k - j - next[1]]);
}
for (int j = 0; j + next[1] <= k; j++)
{
bestAt[j + next[1]] = min(bestAt[j + next[1]], dp[next[0]][j] + 1);
}
}
//for (int j = 0; j <= k; j++) cout << "oj " << i << " " << dp[i][k] << endl;
}
if (res == N) return -1;
return res;
}
