#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const ll MOD = 1e9 + 7;
//IOI 2011 Race
// Problem: https://oj.uz/problem/view/IOI11_race
struct edge {
int b;
int w;
edge(int a = 0, int y = 0) : b(a), w(y) {};
};
int n;
int k;
vector<edge> tree[200005];
map<int, int> dists[200005];
int minK[200005];
void dfs(int x, int p) {
dists[x][0] = 0;
minK[x] = 1e9;
for (edge e : tree[x]) {
int v = e.b;
int c = e.w;
if (v == p) continue;
dfs(v, x);
if (dists[v].size() > dists[x].size()) dists[x].swap(dists[v]);
minK[x] = min(minK[x], minK[v]);
for (auto itr = dists[v].begin(); itr != dists[v].end(); ++itr) {
int d = itr->first;
int ns = itr->second;
if (dists[x].find(k - d - c) != dists[x].end()) {
minK[x] = min(minK[x], ns + 1 + dists[x][k - d - c]);
}
}
for (auto itr = dists[v].begin(); itr != dists[v].end(); ++itr) {
int d = itr->first;
int ns = itr->second;
if (dists[x].find(d + c) != dists[x].end()) dists[x][d + c] = min(dists[x][d + c], ns + 1);
else dists[x][d + c] = ns + 1;
}
}
}
int best_path(int N, int K, int H[][2], int L[]) {
n = N;
k = K;
for (int i = 0; i < n - 1; ++i) {
tree[H[i][0]].push_back(edge(H[i][1], L[i]));
tree[H[i][1]].push_back(edge(H[i][0], L[i]));
}
dfs(0, 0);
if (minK[0] != 1e9) return minK[0];
return -1;
}
