#include "race.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a ? (a = b, true) : false; }
template<class T> bool chmax(T &a, T b) { return a < b ? (a = b, true) : false; }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T L, T R) { while (L != R) cerr << *L << " \n"[next(L) == R], ++L; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
const int MAX_N = 300010, inf = 1e9;
vector<pair<int,int>> edge[MAX_N];
map<ll,int> amp[MAX_N];
int k;
int dfs(int x, int lst = -1, ll len = 0) {
static int dep;
++dep;
DE(x, dep, len);
int res = inf;
auto &cur = amp[x]; cur[len] = dep;
for (auto [u, w] : edge[x]) if (u != lst) {
chmin(res, dfs(u, x, len + w));
auto &nxt = amp[u];
if (cur.size() < nxt.size()) swap(cur, nxt);
for (auto [L, D] : nxt) {
if (cur.count(k + 2 * len - L))
chmin(res, D + cur[k + 2 * len - L] - 2 * dep);
}
for (auto [L, D] : nxt)
if (cur.count(L))
chmin(cur[L], D);
else cur[L] = D;
nxt.clear();
}
// if (false) if (cur.count(k + len)) {
// DE(dep, cur[k + len]);
// chmin(res, cur[k + len] - dep);
// }
--dep;
return res;
}
int best_path(int N, int K, int H[][2], int L[]) {
static int cnt;
assert(++cnt == 1);
for (int i = 0;i+1 < N;++i) {
int a = H[i][0], b = H[i][1], w = L[i];
edge[a].pb(b, w);
edge[b].pb(a, w);
}
k = K;
int res = dfs(0);
return res == inf ? -1 : res;
}
