#include "race.h"
#include <bits//stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<long long, null_type, less<long long>, rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
typedef tree<long long, null_type, less_equal<long long>, rb_tree_tag,
tree_order_statistics_node_update>
ordered_multiset;
#define ll long long
#define ld long double
#define iloop(m, h) for (ll i = m; i != h; i += (m < h ? 1 : -1))
#define jloop(m, h) for (auto j = m; j != h; j += (m < h ? 1 : -1))
#define kloop(m, h) for (auto k = m; k != h; k += (m < h ? 1 : -1))
#define lloop(m, h) for (auto l = m; l != h; l += (m < h ? 1 : -1))
#define iloop_(m, h, g) for (auto i = m; i != h; i += g)
#define jloop_(m, h, g) for (auto j = m; j != h; j += g)
#define kloop_(m, h, g) for (auto k = m; k != h; k += g)
#define lloop_(m, h, g) for (auto l = m; l != h; l += g)
#define getchar_unlocked _getchar_nolock // comment before submission
#define pll pair<ll, ll>
#define plll pair<ll, pll>
#define pllll pair<pll, pll>
#define vll vector<ll>
#define qll queue<ll>
#define dll deque<ll>
#define pqll priority_queue<ll>
#define gll greater<ll>
#define INF 1000000000000000
#define MOD1 1000000007
#define MOD2 998244353
#define MOD3 1000000009
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
ll n, k, an = INF;
vector<pll> adj[200005];
map<ll, ll> stm[200005];
ll cups[200005], cups2[200005];
ll dfs(ll nd, ll pr) {
stm[nd][0] = 0;
vector<pll> mg;
ll crt = nd;
for (auto it : adj[nd]) {
if (it.second != pr) {
mg.push_back({it.first, dfs(it.second, nd)});
}
}
for (auto it : mg) {
bool swp = 0;
if (stm[crt].size() > stm[it.second].size()) {swap(crt, it.second); swp = 1;}
for (auto it2 : stm[crt]) {
if (stm[it.second].find(k - it.first - (it2.first + cups[crt]) - cups[it.second]) != stm[it.second].end()) {
an = min(an, stm[it.second][k - it.first - (it2.first + cups[crt]) - cups[it.second]] + cups2[it.second] + it2.second + cups2[crt] + 1);
}
}
swap(crt, it.second);
if (!swp) {cups2[crt]++, cups[crt] += it.first;}
for (auto it2 : stm[it.second]) {
if (swp) {
if (stm[crt].find(it2.first + cups[it.second] - cups[crt] + it.first) != stm[crt].end()) {
stm[crt][it2.first + cups[it.second] - cups[crt] + it.first] = min(stm[crt][it2.first + cups[it.second] - cups[crt] + it.first], it2.second + cups2[it.second] + 1 - cups2[crt]);
}
else stm[crt][it2.first + cups[it.second] - cups[crt] + it.first] = it2.second + cups2[it.second] + 1 - cups2[crt];
}
else {
if (stm[crt].find(it2.first + cups[it.second] - cups[crt]) != stm[crt].end()) {
stm[crt][it2.first + cups[it.second] - cups[crt]] = min(stm[crt][it2.first + cups[it.second] - cups[crt]], it2.second + cups2[it.second] - cups2[crt]);
}
else stm[crt][it2.first + cups[it.second] - cups[crt]] = it2.second + cups2[it.second] - cups2[crt];
}
}
}
//cout << nd << "," << crt << ":" << cups[crt] << "," << cups2[crt] << "\n";
//for (auto it : stm[crt]) cout << it.first << " " << it.second << "\n";
return crt;
}
int best_path(int N, int K, int H[][2], int L[]) {
n = N, k = K;
iloop(0, n-1) {
adj[H[i][0]].push_back({L[i], H[i][1]});
adj[H[i][1]].push_back({L[i], H[i][0]});
}
dfs(0, -1);
return (an == INF ? -1 : an);
}
