//#include <bits/stdc++.h>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <functional>
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
#define mp make_pair
#define f first
#define s second
#define pb push_back
typedef long long ll;
typedef long double lld;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
const lld pi = 3.14159265358979323846;
#define MAXI (int)2e5+5
vector<int> ad[MAXI];
vector<vector<int>> dp(MAXI,vector<int>(105,1e9));
map<pair<int,int>,int> paths;
int len = 0;
void dfs(int x,int e){
for(auto s: ad[x]){
if(s == e) continue;
dfs(s,x);
for(int i = paths[{s,x}];i<=len;i++){
dp[x][i] = min(dp[x][i],dp[s][i-paths[{s,x}]]+1);
}
}
}
int best_path(int n, int k, int h[][2], int l[]){
len = k;
for(int i = 0;i<n-1;i++){
int u = h[i][0];
int v = h[i][1];
ad[u].push_back(v);
ad[v].push_back(u);
paths.insert({{u,v},l[i]});
paths.insert({{v,u},l[i]});
}
for(int i = 0;i<n;i++){
dp[i][0] = 0;
}
dfs(0,0);
int ans = 1e9;
for(int i = 0;i<n;i++){
ans = min(ans,dp[i][k]);
}
if(ans == 1e9) ans = -1;
return ans;
}
