#include<bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define ST first
#define ND second
ostream& operator<<(ostream &out, string str) {
for(char c : str) out << c;
return out;
}
template<class L, class R> ostream& operator<<(ostream &out, pair<L, R> p) {
return out << "(" << p.ST << ", " << p.ND << ")";
}
template<class T> auto operator<<(ostream &out, T a) -> decltype(a.begin(), out) {
out << "{";
for(auto it = a.begin(); it != a.end(); it = next(it))
out << (it != a.begin() ? ", " : "") << *it;
return out << "}";
}
void dump() { cerr << "\n"; }
template<class T, class... Ts> void dump(T a, Ts... x) {
cerr << a << ", ";
dump(x...);
}
#ifdef DEBUG
# define debug(...) cerr << "[" #__VA_ARGS__ "]: ", dump(__VA_ARGS__)
#else
# define debug(...) false
#endif
template<class T> int size(T && a) { return (int) a.size(); }
using LL = long long;
using PII = pair<int, int>;
#include "race.h"
int best_path(int n, int k, int h[][2], int l[]) {
vector<vector<PII>> adj(n);
REP(i, n - 1) {
adj[h[i][0]].emplace_back(h[i][1], l[i]);
adj[h[i][1]].emplace_back(h[i][0], l[i]);
}
vector<int> sub(n), del(n);
function<void(int, int)> get_sub = [&](int v, int p) {
sub[v] = 1;
for(auto &[u, w] : adj[v]) {
if(u != p && !del[u]) {
get_sub(u, v);
sub[v] += sub[u];
}
}
};
function<int(int, int, int)> get_centro = [&](int v, int p, int tree) {
bool is_centro = true;
if((tree - sub[v]) * 2 > tree)
is_centro = false;
for(auto &[u, w] : adj[v]) {
if(u != p && !del[u]) {
int r = get_centro(u, v, tree);
if(r != -1) return r;
if(sub[u] * 2 > tree)
is_centro = false;
}
}
if(is_centro) return v;
return -1;
};
int inf = 1e9, ans = inf;
vector<int> opt(k + 1, inf);
function<void(int, int, int, int, int)> get_ans = [&](int v, int p, int dep, int dst, int type) {
if(dst > k) return;
if(type == 1) ans = min(ans, dep + opt[k - dst]);
if(type == 2) opt[dst] = min(opt[dst], dep);
if(type == 3) opt[dst] = inf;
for(auto &[u, w] : adj[v])
if(u != p && !del[u])
get_ans(u, v, dep + 1, dst + w, type);
};
function<void(int)> decomp = [&](int v) {
get_sub(v, -1);
v = get_centro(v, -1, sub[v]);
opt[0] = 0;
for(auto &[u, w] : adj[v]) if(!del[u]) {
get_ans(u, v, 1, w, 1);
get_ans(u, v, 1, w, 2);
}
for(auto &[u, w] : adj[v]) if(!del[u])
get_ans(u, v, 1, w, 3);
del[v] = true;
for(auto &[u, w] : adj[v]) if(!del[u])
decomp(u);
};
decomp(0);
if(ans >= inf) ans = -1;
return ans;
}
