#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (auto i = (a); i < (b); ++i)
#define eb(x...) emplace_back(x)
bool ckmin(auto &a, const auto &b) { return a > b ? a = b, 1 : 0; }
using ll = int64_t;
int best_path(int n, int k, int h[][2], int l[]) {
vector<bool> dead(n);
vector<int> mn(k + 1), sz(n);
vector<vector<pair<int, int>>> g(n);
rep(e, 0, n - 1) {
g[h[e][0]].eb(h[e][1], l[e]);
g[h[e][1]].eb(h[e][0], l[e]);
}
int ans = n;
function<int(int)> centroid = [&](int root) {
function<void(int, int)> init = [&](int u, int p) {
sz[u] = 1;
for (auto &[v, d] : g[u])
if (v != p && !dead[v])
init(v, u), sz[u] += sz[v];
};
init(root, -1);
function<int(int, int)> dfs = [&](int u, int p) {
for (auto &[v, d] : g[u])
if (v != p && !dead[v] && 2 * sz[v] > sz[root])
return dfs(v, u);
return u;
};
return dfs(root, -1);
};
function<void(int)> solve = [&](int s) {
int root = centroid(s);
function<void(int, int, int)> clear = [&](int u, int p, int dist) {
if (dist > k) return;
mn[dist] = mn[k - dist] = n;
for (auto &[v, d] : g[u])
if (v != p && !dead[v])
clear(v, u, dist + d);
};
clear(root, -1, 0);
vector<pair<int, int>> lazy; int dep = 1;
function<void(int, int, int)> dfs = [&](int u, int p, int dist) {
if (dist > k) return;
ckmin(ans, dep + mn[k - dist]);
lazy.eb(dist, dep++);
for (auto &[v, d] : g[u]) {
if (v == p || dead[v]) continue;
dfs(v, u, dist + d);
}
--dep;
};
mn[0] = 0;
for (auto &[v, d] : g[root]) {
if (dead[v]) continue;
dfs(v, root, d);
for (auto &[dist, dep] : lazy)
ckmin(mn[dist], dep);
lazy.clear();
}
dead[root] = true;
for (auto &[v, d] : g[root]) if (!dead[v]) solve(v);
};
solve(0);
return ans != n ? ans : -1;
}
