#include "race.h"
#include <bits/stdc++.h>
using namespace std;
namespace
{
template <typename Fun>
struct YCombinator
{
template <typename T>
YCombinator(T &&_fun) : fun(forward<T>(_fun)) {}
template <typename... Args>
decltype(auto) operator()(Args &&...args) { return fun(ref(*this), forward<Args>(args)...); }
private:
Fun fun;
};
template <typename T>
YCombinator(T &&) -> YCombinator<decay_t<T>>;
template <typename T>
bool ckmin(T &lhs, const T &rhs) { return rhs < lhs ? lhs = rhs, 1 : 0; }
template <typename T>
bool ckmax(T &lhs, const T &rhs) { return rhs > lhs ? lhs = rhs, 1 : 0; }
} // namespace
int best_path(int N, int K, int H[][2], int L[])
{
vector<vector<pair<int, int>>> adj(N);
for (int i = 0; i < N - 1; i++)
adj[H[i][0]].emplace_back(H[i][1], L[i]),
adj[H[i][1]].emplace_back(H[i][0], L[i]);
int res = INT_MAX;
YCombinator(
[&](auto self, int u, int p) -> map<int, int>
{
map<int, int> mp;
mp[0] = 0;
for (auto [v, w] : adj[u])
{
if (v != p)
{
map<int, int> mp1 = self(v, u);
mp1[mp1.begin()->first - w] = mp1.begin()->second - 1;
if ((int)mp.size() < (int)mp1.size())
swap(mp, mp1);
for (auto [x, d] : mp1)
{
if (auto it = mp.find(K - x + mp1.begin()->first + mp.begin()->first); it != mp.end())
ckmin(res, d - mp1.begin()->second + it->second - mp.begin()->second);
}
for (auto [x, d] : mp1)
ckmin(mp.emplace(x - mp1.begin()->first + mp.begin()->first, INT_MAX).first->second, d - mp1.begin()->second + mp.begin()->second);
}
}
return mp;
})(0, -1);
return (res != INT_MAX ? res : -1);
}
