#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<ll> check(n+1,0);
matrix<ll> 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<ll(ll,ll,ll,ll,ll,vector<pll>&)> dfs = [&](ll id, ll last, ll sizee, ll dist, ll count, vector<pll>&v){
if(dist != 0)
v.push_back({count,dist});
ll ret = 1, maxi = 0;
for(int i = 0; i < grafo[id].size(); i++){
if(grafo[id][i] == last || check[grafo[id][i]])
continue;
ll cur = dfs(grafo[id][i],id,sizee,dist == 0 ? 0 : dist+peso[id][i],count + 1,v);
maxi = max(maxi, cur);
ret +=cur;
}
maxi = max(maxi,sizee-ret);
if(maxi <= sizee/2)
centroid = id;
return ret;
};
vector<pll> nullv;
ll resp = INF;
function<ll(ll,ll)> findcentroid = [&](ll id, ll sizee){
dfs(id,-1,sizee,0,0,nullv);
int curcen = centroid;
check[curcen] = 1;
map<ll,ll> m;
for(int i = 0; i < grafo[curcen].size(); i++){
if(check[grafo[curcen][i]])
continue;
vector<pll> v;
int subtree = dfs(grafo[curcen][i],-1,0,peso[curcen][i],1,v);
for(pll j : v){
if(m.count(k-j.ss)){
resp = min(resp, m[k-j.ss] + j.ff);
}
}
for(pll 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(0,n);
if(resp == INF)
return -1;
return resp;
}
