#include <bits/stdc++.h>
using namespace std;
static const int INF = 1e9;
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++) {
int u = H[i][0];
int v = H[i][1];
int w = L[i];
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
vector<int> sz(N);
vector<bool> removed(N, false);
int answer = INF;
function<void(int,int)> dfs_size = [&](int u, int p) {
sz[u] = 1;
for (auto [v, w]: adj[u]) {
if (v == p || removed[v]) continue;
dfs_size(v, u);
sz[u] += sz[v];
}
};
function<int(int,int,int)> find_centroid = [&](int u, int p, int tot) {
for (auto [v, w]: adj[u]) {
if (v == p || removed[v]) continue;
if (sz[v] > tot / 2)
return find_centroid(v, u, tot);
}
return u;
};
vector<pair<int,int> > paths;
function<void(int,int,int,int)> dfs_paths =
[&](int u, int p, int dist, int edges) {
if (dist > K) return;
paths.push_back({dist, edges});
for (auto [v, w]: adj[u]) {
if (v == p || removed[v]) continue;
dfs_paths(v, u, dist + w, edges + 1);
}
};
function<void(int)> decompose = [&](int entry) {
dfs_size(entry, -1);
int c = find_centroid(entry, -1, sz[entry]);
removed[c] = true;
unordered_map<int,int> best;
best.reserve(sz[entry] * 2);
best[0] = 0;
for (auto [v, w]: adj[c]) {
if (removed[v]) continue;
paths.clear();
dfs_paths(v, c, w, 1);
for (auto [d, e]: paths) {
auto it = best.find(K - d);
if (it != best.end()) {
answer = min(answer, e + it->second);
}
}
for (auto [d, e]: paths) {
auto it = best.find(d);
if (it == best.end() || it->second > e) {
best[d] = e;
}
}
}
for (auto [v, w]: adj[c]) {
if (!removed[v])
decompose(v);
}
};
decompose(0);
return (answer == INF ? -1 : answer);
}
