#include<bits/stdc++.h>
#include "race.h"
using namespace std;
using vi = vector<int>;
using pi = pair<long long,long long>;
typedef long long ll;
ll ans, k;
vector<ll> depth;
vector<map<ll,int>>paths;
vector<vector<pi>>adjL;
void dfs(int pos, int prev, ll sum) {
paths[pos][sum] = depth[pos];
ll target = k + 2*sum;
for(pi adj: adjL[pos]) {
if(adj.first == prev) continue;
depth[adj.first] = depth[pos] + 1;
dfs(adj.first, pos, sum + adj.second);
if(paths[adj.first].size() > paths[pos].size()) swap(paths[adj.first], paths[pos]);
for(auto it: paths[adj.first]) {
if(paths[pos].find(target - it.first) != paths[pos].end()) {
ll cur = paths[pos][target-(it.first)] + (it.second) - 2 * depth[pos];
if(ans == -1) ans = cur;
else ans = min(ans, cur);
}
}
for(auto it: paths[adj.first]) {
if(paths[pos].find(it.first) == paths[pos].end()) paths[pos].insert(it);
else paths[pos][it.first] = min(paths[pos][it.first], it.second);
}
}
}
int best_path(int N, int K, int H[][2], int L[]) {
ans = -1;
k = K;
paths.resize(N);
depth.assign(N, 0);
adjL.assign(N, vector<pi>());
for(int i=0; i<N-1; ++i) {
adjL[H[i][0]].push_back({H[i][1], L[i]});
adjL[H[i][1]].push_back({H[i][0], L[i]});
}
depth[0] = 1;
dfs(0,0,0);
return ans;
}
