#include <bits/stdc++.h>
//Debug
#define DEBUG_ON false
#define DBG(x) if(DEBUG_ON) cout << "Line(" << __LINE__ << ") -> " << #x << " = " << (x) << "\n";
//Macros
#define rep(i, n) for(int i=0; i<n; i++)
#define pii pair<int, ll>
typedef long long ll;
using namespace std;
//==================================
//GLOBALS
ll TARGET;
const int INF = 1e9;
int BEST;
vector<vector<pii>> graph;
//==================================
void DFS(int p, int node, ll w, int lenght){
//Check
if(w > TARGET) return;
if(w == TARGET) BEST = min(BEST, lenght);
//Neighs
for(auto &v : graph[node]){
if(v.first == p) continue;
DFS(node, v.first, v.second + w, lenght + 1);
}
}
int best_path(int N, int K, int H[][2], int L[]){
//Connect graph
graph.assign(N, vector<pii>{});
int a, b;
ll w;
rep(i, N-1){
a= H[i][0], b= H[i][1], w= L[i];
graph[a].push_back({b, w});
graph[b].push_back({a, w});
}
//Solve
BEST = INF;
TARGET = K;
rep(i, N)
DFS(-1, i, 0, 0);
return (BEST != INF) ? BEST : -1;
}
//==================================
