#include "race.h"
#include <bits/stdc++.h>
using namespace std;
void dfs(int x, int p, vector<vector<pair<int, int>>> &AR, map<int, int> &dp, int K, int prof, int prof2, int &best)
{
map<int, int> M;
M[prof] = prof2;
for (int i = 0; i < AR[x].size(); i++)
{
if (AR[x][i].first == p)
continue;
dfs(AR[x][i].first, x, AR, dp, K, prof + AR[x][i].second, prof2 + 1, best);
if (dp.size() > M.size())
swap(dp, M);
for (auto j : dp)
{
M[j.first] = 1000000;
M[j.first] = min(M[j.first], j.second);
if (M[K - j.first + 2 * prof] > 0)
best = min(best, M[K - j.first + 2 * prof] + j.second - 2 * prof2);
else
M.erase(K - j.first + 2 * prof);
if (j.first - prof == K)
best = min(best, j.second - prof2);
}
}
swap(dp, M);
}
int best_path(int N, int K, int H[][2], int L[])
{
vector<vector<pair<int, int>>> AR(N);
for (int i = 0; i < N - 1; i++)
{
AR[H[i][0]].push_back({H[i][1], L[i]});
AR[H[i][1]].push_back({H[i][0], L[i]});
};
map<int, int> dp;
int best = 1000000;
dfs(0, 0, AR, dp, K, 0, 0, best);
return ((best == 1000000) ? -1 : best);
}
/*int main()
{
int N, K;
cin >> N >> K;
int L[N], H[N][2];
for (int i = 0; i < N - 1; i++)
{
cin >> H[i][0] >> H[i][1];
}
for (int i = 0; i < N - 1; i++)
{
cin >> L[i];
}
cout << best_path(N, K, H, L);
}*/
