Escape Among Islands

In this problem, there is a tree of n islands connected by n‐1 bidirectional sea routes. Each route takes a certain number of days to traverse – and every day at sea consumes one unit of food. The escaping person, a (Little E), must buy a backpack that can hold exactly k units of food; note that the cost of such a backpack is k (in ten‐thousands of yuan). Because he can refill supplies instantly and arbitrarily at any island, his only limitation is that every single route he takes must require no more food than his backpack capacity. That is, he can only travel an edge if its travel time is ≤ k.

At time 0, a starts his escape from island 1. His pursuer, b (PF), will start chasing from the same island at time t seconds. PF knows the official network (the tree) and will compute his travel times along these given routes. Moreover, PF is allowed to build exactly one extra bidirectional route (or none) between any two islands u and v if the following conditions hold:

• The travel time between u and v along the tree is at most d.
• There are at least q intermediate islands on the unique tree path between u and v (i.e. the total number of vertices on the path is at least q+2).

If an extra route is built between u and v, its travel time is defined to be \(\left\lfloor \frac{time(u \to v)}{2} \right\rfloor\) (in days), where time(u \to v) is the sum of travel times along the unique path in the tree. PF will choose the extra route in order to minimize his arrival times – that is, after adding the extra edge, his travel time to each island i is \(t+ d_{PF}(i)\) (where d_PF(i) is the shortest time from island 1 to island i in the modified graph).

Meanwhile, Little E (who is restricted by his backpack capacity k) can only travel via tree edges whose individual travel times are ≤ k; thus, his travel time to an island is the sum of the weights along the unique tree path from island 1 (provided all edges along that path satisfy the capability constraint). He is safe on island i if his arrival time (using the tree path) is strictly less than PF’s arrival time \(t+d_{PF}(i)\) (if they arrive simultaneously then he is caught).

Your task is to help Little E by computing the minimum possible k such that, even if PF chooses his extra route optimally (from all eligible extra routes including the option of building none), there exist at least l islands which Little E can reach safely (i.e. his travel time is strictly less than PF’s). In case there are several possible k values achieving this, note that Little E would like the maximum pairwise distance (along tree paths) among the islands he can reach safely to be as small as possible – however, you only need to output the minimum required k.

Input/Output Format:

inputFormat

The first line contains five integers: n, l, t, d and q — the number of islands, the required number of safe islands, the head‐start time for Little E, the maximum allowed travel time for an extra route, and the minimum number of intermediate islands required on the tree path, respectively.

The next n-1 lines each contain three integers u, v and w, indicating that there is a bidirectional sea route between islands u and v with travel time w (in days).

outputFormat

Output a single integer: the minimum k such that Little E can safely reach at least l islands even under PF’s optimal extra route construction.

sample

5 3 3 10 0
1 2 2
1 3 3
2 4 4
3 5 5

3