#include <bits/stdc++.h>
using namespace std;
template<typename TH>
void _dbg(const char* sdbg, TH h)
{
cerr << sdbg << " = " << h << "\n";
}
template<typename TH, typename... TA>
void _dbg(const char* sdbg, TH h, TA... t)
{
while (*sdbg != ',') cerr << *sdbg++;
cerr << " = " << h << ",";
_dbg(sdbg + 1, t...);
}
#define db(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#define chkpt cerr << "--- Checkpoint here ---\n";
const int N=2e5+5,K=1e6+6,INF=1e9;
struct Edge{
int u,v,w;
int Adj(int x){
return u^v^x;
}
};
int n,k;
Edge edgeList[N];
vector<int> g[N];
int d[5005][5005],f[5005][5005];
void DFS(int u,int fa,int r){
for(int id:g[u]){
int v=edgeList[id].Adj(u);
if(v!=fa){
d[r][v]=d[r][u]+edgeList[id].w;
f[r][v]=f[r][u]+1;
DFS(v,u,r);
}
}
}
int Sub2(){
for(int i=1;i<=n;++i){
DFS(i,-1,i);
}
int res=INF;
for(int i=1;i<=n;++i){
for(int j=i+1;j<=n;++j){
if(d[i][j]==k){
res=min(res,f[i][j]);
}
}
}
return (res==INF?-1:res);
}
int best_path(int N,int K,int H[][2],int L[])
{
n=N;
k=K;
for(int i=0;i<=n-2;++i){
int u=H[i][0]+1,v=H[i][1]+1;
g[u].push_back(i+1);
g[v].push_back(i+1);
edgeList[i+1]={u,v,0};
}
for(int i=0;i<=n-2;++i){
edgeList[i+1].w=L[i];
}
return Sub2();
}
//int main()
//{
// freopen("IOI11_race.inp","r",stdin);
// ios_base::sync_with_stdio(0);
// cin.tie(0);
// cin>>n>>k;
// for(int i=1;i<=n-1;++i){
// int u,v;
// cin>>u>>v;
// u++;
// v++;
// g[u].push_back(i);
// g[v].push_back(i);
// edgeList[i]={u,v,0};
// }
// for(int i=1;i<=n-1;++i){
// cin>>edgeList[i].w;
// }
// Sub2();
// return 0;
//}
