#include "race.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int INF=1e9;
int better(int a,int b){
if(!a){
return b;
}
if(!b){
return a;
}
return min(a,b);
}
int KMAX;
vector<vector<pair<int,int>>>adj;
map<pair<int,int>,vector<int>>mem;
vector<int>dfs(int u,int p=-1){
if(mem.count({u,p})){
return mem[{u,p}];
}
mem[{u,p}].resize(KMAX+1);
vector<int>&res=mem[{u,p}];
for(auto[v,l]:adj[u]){
if(v==p){
continue;
}
vector<int>x=dfs(v,u);
for(int i=l;i<=KMAX;i++){
if(i-l>0&&!x[i-l]){
continue;
}
res[i]=better(res[i],x[i-l]+1);
}
}
return res;
}
int best_path(int N, int K, int H[][2], int L[])
{
KMAX=K;
adj.resize(N);
for(int i=0;i<N-1;i++){
auto[u,v]=H[i];
int l=L[i];
adj[u].push_back({v,l});
adj[v].push_back({u,l});
}
int res=0;
for(int u=0;u<N;u++){
res=better(res,dfs(u)[K]);
}
return (res?res:-1);
}
