#include "race.h"
#include <bits/stdc++.h>
const int INF = 1e9;
using namespace std;
using pii = pair<int, int>;
using LL = long long;
#define pb push_back
int best_path(int N, int K, int H[][2], int L[]) {
LL ans = INF;
vector e(N, vector<pii>());
for (int i = 0; i < N - 1; i++) {
int x = H[i][0], y = H[i][1], d = L[i];
e[x].pb({y, d});
e[y].pb({x, d});
}
vector<bool> v(N), sub(N);
auto cen_decomp = [&](auto cen_decomp, int g, int SZ) -> void {
auto dfs_sub = [&](auto dfs_sub, int g, int p) -> void {
sub[g] = 1;
for (auto [u, d] : e[g]) if (u != p && !v[u]) {
dfs_sub(dfs_sub, u, g);
sub[g] += sub[u];
}
};
auto find_cen = [&](auto find_cen, int g, int p) -> void {
for (auto [u, d] : e[g]) if (u != p && !v[u]) {
if (sub[u] * 2 >= SZ)
return find_cen(find_cen, u, g);
}
};
dfs_sub(dfs_sub, g, -1);
g = find_cen(find_cen, g, -1);
dfs_sub(dfs_sub, g, -1);
v[g] = 1;
map<LL, LL> dp;
auto fill_dp = [&](auto fill_dp, int g, int p, int L, int d) {
if (!dp.count(L)) {
dp[L] = d;
} else {
dp[L] = min(dp[L], (LL)d);
}
for (auto [u, nl] : e[g]) if (!v[u] && u != p) {
fill_dp(fill_dp, u, g, L + nl, d + 1);
}
};
auto compare_dp = [&](auto compare_dp, int g, int p, int L, int d) {
if (dp.count(K - L)) {
ans = min(ans, d + dp[K - L]);
}
for (auto [u, nl] : e[g]) if (!v[u] && u != p) {
compare_dp(compare_dp, u, g, L + nl, d + 1);
}
};
for (auto [u, d] : e[g]) if (!v[u]) {
compare_dp(compare_dp, u, g, d, 1);
fill_dp(fill_dp, u, g, d, 1);
}
for (auto [u, d] : e[g]) if (!v[u]) {
cen_decomp(cen_decomp, u, sub[u]);
}
};
return (ans >= INF ? -1 : ans);
}
