#include <bits/stdc++.h>
using namespace std;
const int inf = 2e9;
int best_path(int n, int k, int h[][2], int l[]) {
vector<vector<pair<int, int>>> g(n + 1);
for (int i = 0; i < n - 1; i++) {
g[h[i][0]].emplace_back(h[i][1], l[i]);
g[h[i][1]].emplace_back(h[i][0], l[i]);
}
vector<int> sz(n + 1);
vector<int> vis(n + 1);
auto dfs_sz = [&](auto dfs_sz, int u, int p) -> void {
sz[u] = 1;
for (auto [v, w] : g[u]) {
if (v != p and !vis[v]) {
dfs_sz(dfs_sz, v, u);
sz[u] += sz[v];
}
}
};
auto find_c = [&](auto find_c, int u, int p, int tot) -> int {
for (auto [v, w] : g[u]) {
if (v != p and !vis[v] and sz[v] > tot / 2) {
return find_c(find_c, v, u, tot);
}
}
return u;
};
int ans = inf;
vector<int> mods;
vector<int> min_e(k + 1, inf);
min_e[0] = 0;
auto calc = [&](auto calc, int u, int p, int cw, int ce, int upd) -> void {
if (cw > k) {
return;
}
if (upd == 1) {
if (min_e[cw] > ce) {
min_e[cw] = ce;
mods.emplace_back(cw);
}
} else {
ans = min(ans, ce + min_e[k - cw]);
}
for (auto [v, w] : g[u]) {
if (!vis[v] and v != p) {
calc(calc, v, u, cw + w, ce + 1, upd);
}
}
};
auto solve = [&](auto solve, int u) -> void {
dfs_sz(dfs_sz, u, -1);
int c = find_c(find_c, u, -1, sz[u]);
vis[c] = 1;
for (auto [v, w] : g[c]) {
if (!vis[v]) {
calc(calc, v, c, w, 1, 0);
calc(calc, v, c, w, 1, 1);
}
}
for (int &x : mods) {
min_e[x] = inf;
}
mods.clear();
for (auto [v, w] : g[c]) {
if (!vis[v]) {
solve(solve, v);
}
}
};
solve(solve, 0);
if (ans == inf) {
return -1;
} else {
return ans;
}
}
