#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<int>> g(n);
rep(e, 0, n - 1) g[h[e][0]].eb(e), g[h[e][1]].eb(e);
int ans = n;
function<int(int)> centroid = [&](int root) {
function<void(int, int)> init = [&](int u, int p) {
sz[u] = 1;
for (int e : g[u]) {
int v = h[e][u != h[e][1]];
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 (int e : g[u]) {
int v = h[e][u != h[e][1]];
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 (int e : g[u]) {
int v = h[u][e != h[u][1]];
if (v != p && !dead[v])
clear(v, u, dist + l[e]);
}
};
clear(root, -1, 0);
vector<pair<int, int>> lazy; int dep = 0;
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 (int e : g[u]) {
int v = h[u][e != h[u][1]];
if (v == p || dead[v]) continue;
dfs(v, u, dist + l[e]);
if (u != root) continue;
for (auto [dist, dep] : lazy)
ckmin(mn[dist], dep);
lazy.clear();
}
--dep;
};
mn[0] = 0; dfs(root, -1, 0);
dead[root] = true;
for (int e : g[root]) {
int v = h[e][root != h[e][1]];
if (!dead[v]) solve(v);
}
};
solve(0);
return ans != n ? ans : -1;
}
