#include "race.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 2e5 + 5;
const int MAX_K = 1e2 + 5;
vector< vector<pair<int, int> > > g (MAX_N);
int dp [MAX_N][MAX_K];
int delta;
int mn = numeric_limits<int>::max();
void dfs (int node, int p = -1) {
for (auto to : g[node]) {
if (to.first != p) dfs (to.first, node);
}
dp[node][0] = 0;
for (auto to : g[node]) {
if (to.first == p) continue;
int vertex = to.first;
int w = to.second;
// Do with the others
for (int i = 0; i <= delta; i++) {
int other = delta - i - w;
if (other >= 0) mn = min (mn, dp[node][i] + dp[vertex][other] + 1);
}
// Add path
for (int i = 0; i <= delta; i++) {
if (i - w >= 0) dp[node][i] = min (dp[node][i], 1 + dp[vertex][i - w]);
}
}
mn = min (mn, dp[node][delta]);
}
int best_path(int N, int K, int H[][2], int L[]) {
delta = K;
for (int i = 0; i < N - 1; i++) {
int st = H[i][0];
int et = H[i][1];
int w = L[i];
g[st].emplace_back(et, w);
g[et].emplace_back(st, w);
}
for (int i = 0; i < MAX_N; i++) {
for (int j = 0; j < MAX_K; j++) {
dp[i][j] = 1e9;
}
}
dfs (0);
return (mn > 1e8 ? -1 : mn);
}
