#include <bits/stdc++.h>
using namespace std;
// #define int int64_t
int min(int a, int b) {
return (a < b ? a : b);
}
int max(int a, int b) {
return (a < b ? b : a);
}
const int inf = 2e9;
int best_path(int n, int k, int h[][2], int l[]) {
// ios :: sync_with_stdio(false);
// cin.tie(nullptr);
// int n, k;
// cin >> n >> k;
// vector<int> l(n);
// vector<pair<int, int>> h(n);
// for (int i = 1; i <= n - 1; i++) {
// cin >> h[i].first >> h[i].second;
// }
// for (int i = 1; i <= n - 1; i++) {
// cin >> l[i];
// }
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> edit;
vector<int> E(k + 1, inf);
E[0] = 0;
auto calc = [&](auto calc, int u, int p, int W, int e, int upd) -> void {
if (W > k)
return;
if (upd == 1) {
if (E[W] > e) {
E[W] = e;
edit.emplace_back(W);
}
} else {
ans = min(ans, e + E[k - W]);
}
for (auto [v, w] : g[u]) {
if (!vis[v] and v != p) {
calc(calc, v, u, W + w, e + 1, upd);
}
}
};
auto solve = [&](auto solve, int u) -> void {
dfs_sz(dfs_sz, u, -1);
int centroid = find_c(find_c, u, -1, sz[u]);
vis[centroid] = 1;
for (auto [v, w] : g[centroid]) {
if (!vis[v]) {
calc(calc, v, centroid, w, 1, 0);
calc(calc, v, centroid, w, 1, 1);
}
}
for (int &x : edit) {
E[x] = inf;
}
edit.clear();
for (auto [v, w] : g[centroid]) {
if (!vis[v]) {
solve(solve, v);
}
}
};
solve(solve, 0);
if (ans == inf) {
return -1;
} else {
return ans;
}
}
