#include<bits/stdc++.h>
#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second
using namespace std;
template <typename T>
using matrix = vector<vector<T>>;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INFL = (1LL<<62)-1;
const int INF = (1<<30)-1;
const double EPS = 1e-7;
const int MOD = 1e9 + 7;
const int MAXN = 1e6+1;
int best_path(int n, int k, int h[][2], int l[]){
vector<int> check(n+1,0);
matrix<int> grafo(n+1), peso(n+1);
for(int i = 0; i < n-1; i++)
grafo[h[i][0]].push_back(h[i][1]), grafo[h[i][1]].push_back(h[i][0]), peso[h[i][0]].push_back(l[i]), peso[h[i][1]].push_back(l[i]);
int centroid;
function<int(int,int,int,int,int,vector<pii>&)> dfs = [&](int id, int last, int sizee, int dist, int count, vector<pii>&v){
if(dist == 0)
dist--;
else v.push_back({count,dist});
int ret = 1, maxi = 0;
for(int i = 0; i < grafo[id].size(); i++){
if(grafo[id][i] == last || check[grafo[id][i]])
continue;
int cur = dfs(grafo[id][i],id,sizee,min(dist+peso[id][i],(int)1e7),count + 1,v);
maxi = max(maxi, cur);
ret +=cur;
}
maxi = max(maxi,sizee-ret);
if(maxi <= sizee/2)
centroid = id;
return ret;
};
vector<pii> nullv;
int resp = INF;
function<int(int,int)> findcentroid = [&](int id, int sizee){
dfs(id,0,sizee,0,0,nullv);
int curcen = centroid;
check[curcen] = 1;
unordered_map<int,int> m;
for(int i = 0; i < grafo[curcen].size(); i++){
if(check[grafo[curcen][i]])
continue;
vector<pii> v;
int subtree = dfs(grafo[curcen][i],0,0,peso[curcen][i],1,v);
for(pii j : v){
if(m.count(k-j.ss)){
resp = min(resp, m[k-j.ss] + j.ff);
}
}
for(pii j : v){
if(m.count(j.ss)){
m[j.ss] = min(m[j.ss], j.ff);
} else m[j.ss] = j.ff;
}
findcentroid(grafo[curcen][i],subtree);
}
if(m.count(k))
resp = min(resp,m[k]);
return curcen;
};
findcentroid(1,n);
if(resp == INF)
return -1;
return resp;
}
