#pragma GCC optimize("Ofast")
#pragma GCC optimization ("unroll-loops")
#include<bits/stdc++.h>
using namespace std;

const int V = 3e5;


int vals[V];
int best_path(int N, int K, int H[][2], int L[]) {
	mt19937 rng(47);
	const int INF = 1e9;
	int ans = INF;

	vector<int> perm(N); iota(perm.begin(), perm.end(), 0);
	shuffle(perm.begin(), perm.end(), rng);

	vector<vector<pair<int, int>>> adj(N);
	for (int i = 0; i+1 < N; ++i) {
		// cout << h[i][0] << ' ' << h[i][1] << endl;
		adj[perm[H[i][0]]].push_back({perm[H[i][1]], L[i]});
		adj[perm[H[i][1]]].push_back({perm[H[i][0]], L[i]});
	}

	vector<bool> deleted(N);
	vector<pair<int, int>> max_sub(N);
	auto dfs = [&](auto&& self, int cur, int prv) -> int {
		int sz = 1;
		max_sub[cur] = {0, -1};
		for (auto [nxt, weight] : adj[cur]) {
			if (nxt == prv || deleted[nxt]) continue;
			int cur_sz = self(self, nxt, cur);
			sz += cur_sz;
			max_sub[cur] = max(max_sub[cur], {cur_sz, nxt});
		}
		return sz;
	};

	auto get_dist = [&](auto& self, int cur, int prv, int depth, int level, auto& path) -> void {
		if (depth > K || level >= ans) return;
		path.push_back({depth, level});
		for (auto [nxt, weight] : adj[cur]) {
			if (nxt == prv || deleted[nxt]) continue;
			self(self, nxt, cur, depth + weight, level + 1, path);
		}
	};

	auto rec = [&](auto&& self, int cur) -> void {
		int total_sz = dfs(dfs, cur, -1);
		while (max_sub[cur].first * 2 > total_sz) cur = max_sub[cur].second;

		deleted[cur] = true;

		for (int i = 0; i <= K; ++i) vals[i] = INF;
		for (auto [nxt, weight] : adj[cur]) {
			if (deleted[nxt]) continue;

			vector<pair<int, int>> path; path.reserve(total_sz);
			get_dist(get_dist, nxt, cur, weight, 1, path);
	
			for (auto [dist, level] : path) {
				ans = min(ans, vals[K - dist] + level);
				if (vals[K - dist] == INF && dist == K) {
					ans = min(ans, level);
				}
			}

			for (auto [dist, level] : path) {
				vals[dist] = min(vals[dist], level);
			}
		}

		for (auto [nxt, weight] : adj[cur]) {
			if (deleted[nxt]) continue;
			self(self, nxt);
		}
	};

	rec(rec, 0);

	return (ans == INF ? -1 : ans);
}