#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
vector < set < pair <int, int> > > G(200005);
int dp[200005];
int h[200005];
int h2[200005];
int best[1000005];
int n, k, rez;
void dfs(int nod, int t){
dp[nod] = 1;
for(auto x : G[nod]){
if(x.first == t) continue;
dfs(x.first, nod);
dp[nod] += dp[x.first];
}
}
int centroid(int nod, int t, int sz){
for(auto x : G[nod]){
if(x.first == t) continue;
if(dp[x.first] > (sz >> 1)) return centroid(x.first, nod, sz);
}
return nod;
}
void dfs2(int nod, int t, int flag){
if(!flag) rez = min(rez, h[nod] + best[k - h2[nod]]);
else if(flag == 1) best[h2[nod]] = min(best[h2[nod]], h[nod]);
else best[h2[nod]] = inf;
for(auto x : G[nod]){
if(x.first == t) continue;
h2[x.first] = h2[nod] + x.second;
h[x.first] = h[nod] + 1;
if(h2[x.first] > k) continue;
dfs2(x.first, nod, flag);
}
}
void build_centroid_tree(int nod){
dfs(nod, 0);
int c = centroid(nod, 0, dp[nod]);
h[c] = h2[c] = 0;
for(auto x : G[c]){
h2[x.first] = h2[c] + x.second;
h[x.first] = h[c] + 1;
if(h2[x.first] > k) continue;
dfs2(x.first, c, 0);
dfs2(x.first, c, 1);
}
rez = min(rez, best[k]);
dfs2(c, 0, 2);
vector <int> v;
for(auto x : G[c]) v.push_back(x.first);
G[c].clear();
for(auto x : v){
G[x].erase(G[x].lower_bound({c, 0}));
build_centroid_tree(x);
}
}
int best_path(int N, int K, int H[][2], int L[]){
int i;
rez = inf;
n = N;
k = K;
for(i = 0; i < n - 1; i++){
H[i][0]++;
H[i][1]++;
G[H[i][0]].insert({H[i][1], L[i]});
G[H[i][1]].insert({H[i][0], L[i]});
}
memset(best, 0x3f, sizeof best);
build_centroid_tree(1);
if(rez == inf) return -1;
return rez;
}
