#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double dou;
#define pii pair<int, int>
#define pb push_back
#define fi first
#define se second
//const ll mod = 1e9+7;
bool maximize(ll &x, ll y ){
if (x < y) {x = y; return true;};
return false;
}
bool minimize(int &x, int y){
if (x > y) {x = y; return true;}
return false;
}
//void add(ll &x, ll y ){
// x += y;
// if (x >= mod) x -= mod;
//}
//void sub(ll &x, ll y) {
// x -= y;
// if (x < 0) x += mod;
//}
const int maxn = 2e5+5;
const int maxx = 1e9+7;
int n, k;
vector<pii> a[maxn];
bitset<maxn> del;
int child[maxn];
int sz, root;
int ans = maxx;
void couchild(int u, int p) {
child[u] = 1;
for (int i = 0; i <(int)a[u].size(); i++) {
int v = a[u][i].fi;
if (v == p || del[v]) continue;
couchild(v, u);
child[u] += child[v];
}
// cout << u << ' ' << child[u] << endl;
}
int centroid(int u, int p) {
for (int i = 0 ;i < (int)a[u].size(); i++) {
int v = a[u][i].fi;
if (v == p || del[v]) continue;
if (child[v] >= (sz >> 1)) return centroid(v, u);
}
return u;
}
int h[maxn];
int dis[maxn];
int tk[1000007];
vector<pii> temp;
void dfs(int u, int p) {
temp.push_back({dis[u], h[u]});
if (tk[k-dis[u]] < maxx) {
minimize(ans, h[u] + tk[k-dis[u]]);
}
for (int i = 0; i < (int)a[u].size(); i++) {
int v = a[u][i].fi;
if (v == p || del[v]) continue;
int w = a[u][i].se;
if (dis[u] + w > k) continue;
dis[v] = dis[u] + w;
h[v] = h[u] + 1;
dfs(v, u);
}
}
void dfsr(int u, int p) {
tk[dis[u]] = maxx;
for (int i = 0; i < (int)a[u].size(); i++) {
int v = a[u][i].fi;
if (v == p || del[v]) continue;
int w = a[u][i].se;
if (dis[u] + w > k) continue;
dfsr(v, u);
}
}
void solve(int u) {
couchild(u, 0);
sz = child[u];
if (sz == 1) {
del[u] = true;
return;
}
//get centroid
root = centroid(u, 0);
// cout << root << endl;
// system("pause");
//dfs solve
h[root] = dis[root] = 0;
for (int i = 0; i < (int)a[root].size(); i++) {
int v = a[root][i].first, w = a[root][i].se;
if (del[v]) continue;
if (w > k) continue;
dis[v] = dis[root] + w;
h[v] = h[root]+1;
dfs(v, root);
for (int i = 0; i < (int)temp.size(); i++) {
minimize(tk[temp[i].fi], temp[i].se);
}
temp.clear();
}
//dfs erase
dfsr(root, 0);
del[root] = true;
//solve sub
for (int i = 0; i < (int)a[root].size(); i++) {
int v = a[root][i].first;
if (del[v]) continue;
solve(v);
}
}
int best_path(int N, int K, int H[][2], int L[]) {
n = N;
k = K;
for (int i = 1; i < n; i++) {
int u = H[i][0], v = H[i][1];
int w = L[i];
++u;
++v;
a[u].pb({v, w});
a[v].pb({u, w});
}
for (int i = 1; i <= k; i++) {
tk[i] = maxx;
}
solve(1);
return (ans >= maxx ? -1 : ans);
}
//int N, K, H[maxn][2], L[maxn];
//
//int main() {
// ios_base::sync_with_stdio(0);
// cin.tie(0);
// cin >> N >> K;
// for (int i = 1; i < N; i++) {
// cin >> H[i][0] >> H[i][1];
// }
// for (int i = 1; i < N; i++) {
// cin >> L[i];
// }
// cout << best_path(N, K, H, L);
//}
/*
4 3
0 1
1 2
1 3
1
2
4
3 3
0 1
1 2
1
1
11 12
0 1
0 2
2 3
3 4
4 5
0 6
6 7
6 8
8 9
8 10
3
4
5
4
6
3
2
5
6
7
*/
