#include "race.h"
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;
#define pii pair<int,int>
vector<int> dp[105];
vector<int> suf[105];
vector<vector<pii>> g;
int ans;
void dfs(int v,int p){
dp[0][v]=0;
for(auto k : g[v]){
if(k.first != p){
for(int i=0;i<=100 - k.second;i++){
if(dp[i][v] != INT_MAX)
dp[i+k.second][k.first] = min(dp[i+k.second][k.first], dp[i][v]+1);
}
dfs(k.first,v);
for(int i=0;i<=100 - k.second;i++){
if(suf[i][k.first] != INT_MAX){
dp[i+k.second][v] = min(dp[i+k.second][v], suf[i][k.first]+1);
suf[i+k.second][v] = min(suf[i+k.second][v], suf[i][k.first]+1);
}
}
}
}
suf[0][v]=0;
}
int best_path(int N, int K, int H[][2], int L[]){
g.clear();
g.resize(N);
ans = INT_MAX;
for(int i=0;i<=100;i++){
dp[i].clear();
suf[i].clear();
dp[i].resize(N, INT_MAX);
suf[i].resize(N, INT_MAX);
}
for(int i=0;i<N-1;i++){
g[H[i][0]].push_back({H[i][1], L[i]});
g[H[i][1]].push_back({H[i][0], L[i]});
}
dfs(0,-1); // запускаем с вершины 0
for(int i=0;i<N;i++){
ans = min(ans, dp[K][i]);
}
if(ans == INT_MAX) return -1;
return ans;
}
