#include <bits/stdc++.h>
#define endl '\n'
#define fi first
#define se second
#define eb emplace_back
#define pb push_back
#define ALL(A) A.begin(), A.end()
#define FOR(i, l, r) for (int i = l; i <= r; i++)
#define FOR2(i, l, r) for (int i = l; i >= r; i--)
#define ce cout<<endl;
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
using pii = pair<int, int>;
using str = string;
using T = pair<ll,int>;
const ll INF = 1e18;
const int N = 2e5;
const int MAXM = 4200005;
const int LOG2 = 17;
const int inv = 1112;
const int MOD =998244353 ;
int dx[]= {0,0,-1,1};
int dy[] = {1 , - 1 , 0 , 0};
// Author : T_Danh - Tri An High School
vector<pii> adj[N + 1];
int res = 1e9;
unordered_map<int, int> dfs(int u, int p, int k) {
unordered_map<int, int> cur;
cur[0] = 0; // Đường đi tại chính node u có độ dài 0, số cạnh 0
for (auto& edge : adj[u]) {
int v = edge.fi;
int w = edge.se;
if (v == p) continue;
unordered_map<int, int> tmp_map = dfs(v, u, k);
// Tạo một map mới để lưu thông tin từ con v đã cộng thêm cạnh (u, v)
unordered_map<int, int> processed_tmp;
for (auto& [val, d] : tmp_map) {
if (val + w <= k) {
processed_tmp[val + w] = d + 1;
}
}
// Đảm bảo cur luôn là map lớn hơn để tối ưu thời gian gộp
if (cur.size() < processed_tmp.size()) swap(cur, processed_tmp);
// 1. Kiểm tra kết quả: Kết hợp nhánh mới (processed_tmp) với các nhánh cũ (cur)
for (auto& [v_val, v_d] : processed_tmp) {
if (cur.count(k - v_val)) {
res = min(res, v_d + cur[k - v_val]);
}
}
// 2. Cập nhật: Đưa nhánh mới vào map tổng cur
for (auto& [v_val, v_d] : processed_tmp) {
if (cur.find(v_val) == cur.end() || v_d < cur[v_val]) {
cur[v_val] = v_d;
}
}
}
return cur;
}
int best_path(int n ,int k ,int H[][2],int L[] ) {
FOR(i,0,n-1){
adj[H[i][0]].eb(H[i][1] , L[i]);
adj[H[i][1]].eb(H[i][0] , L[i]);
}
dfs(0 , -1 , k);
return res;
}
// int main() {
// ios::sync_with_stdio(0);
// cin.tie(0); cout.tie(0);
// #define NAME "runaway"
// if (fopen(NAME ".in", "r"))
// freopen(NAME ".in", "r", stdin),
// freopen(NAME ".out", "w", stdout);
// solve();
// return 0;
// }
