#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>,map<int,int>>mem;
map<int,int>dfs(int u,int p){
if(mem.count({u,p})){
return mem[{u,p}];
}
map<int,int>&res=mem[{u,p}];
res[0]=0;
for(auto[v,l]:adj[u]){
if(v==p){
continue;
}
for(auto[s,c]:dfs(v,u)){
if(s+l>KMAX){
continue;
}
res[s+l]=better(res[s+l],c+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++){
for(auto[v,l]:adj[u]){
//cout<<"! "<<u<<" "<<v<<" "<<dfs(v,u)[K]<<"\n";
res=better(res,dfs(v,u)[K]);
}
}
return (res?res:-1);
}
