#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<ll, ll> pii;
const ll MOD = 1e9 + 7;
//IOI 2011 Race
// Problem: https://oj.uz/problem/view/IOI11_race
struct edge {
ll b;
ll w;
edge(ll a = 0, ll y = 0) : b(a), w(y) {};
};
vector<edge> tree[200005];
map<ll, ll> dists[200005];
ll minK[200005];
ll addTo[200005]; //d + addTo[x] = trueDist;
ll addN[200005]; //ns + addN[x] = trueNs;
void dfs(ll x, ll p, ll k) {
dists[x][0] = 0;
minK[x] = 1e9;
addTo[x] = 0;
addN[x] = 0;
if (k == 0) minK[x] = 0;
for (edge e : tree[x]) {
ll v = e.b;
ll c = e.w;
if (v == p) continue;
dfs(v, x, k);
minK[x] = min(minK[x], minK[v]);
if (dists[v].size() <= dists[x].size()) {
for (auto itr = dists[v].begin(); itr != dists[v].end(); ++itr) {
ll d = itr->first + addTo[v];
ll ns = itr->second + addN[v];
if (dists[x].find(k - d - c - addTo[x]) != dists[x].end()) minK[x] = min(minK[x], ns + 1 + dists[x][k - d -c - addTo[x]] + addN[x]);
}
for (auto itr = dists[v].begin(); itr != dists[v].end(); ++itr) {
ll d = itr->first + addTo[v];
ll ns = itr->second + addN[v];
if (dists[x].find(d + c - addTo[x]) != dists[x].end()) dists[x][d + c - addTo[x]] = min(dists[x][d + c - addTo[x]], ns + 1 - addN[x]);
else dists[x][d + c - addTo[x]] = ns + 1 - addN[x];
}
}
else {
dists[x].swap(dists[v]);
for (auto itr = dists[v].begin(); itr != dists[v].end(); ++itr) {
ll d = itr->first + addTo[x];
ll ns = itr->second + addN[x];
if (dists[x].find(k - d - c - addTo[v]) != dists[x].end()) minK[x] = min(minK[x], ns +1 + dists[x][k - d - c - addTo[v]] + addN[v]);
}
for (auto itr = dists[v].begin(); itr != dists[v].end(); ++itr) {
ll d = itr->first + addTo[x] - addTo[v] - c;
ll ns = itr->second + addN[x] - addN[v] - 1;
if (dists[x].find(d) != dists[x].end()) dists[x][d] = min(dists[x][d], ns);
else dists[x][d] = ns;
}
addTo[x] = addTo[v] + c;
addN[x] = addN[v] + 1;
}
}
}
int best_path(int N, int K, int H[][2], int L[]) {
for (ll 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, K);
if (minK[0] != 1e9) return minK[0];
return -1;
}
//ll main() {
// ios::sync_with_stdio(0);
// cin.tie(0);
//
// ll H[10][2] = { {0,1}, {0,2}, {2,3}, {3,4}, {4,5}, {0,6}, {6,7}, {6,8}, {8,9}, {8,10} };
// ll L[10] = { 3,4,5,4,6,3,2,5,6,7};
// cout << best_path(11, 12, H, L) << endl;
//
//
// return 0;
//}
