Description

Little E's escape route can be viewed as occurring on $n$ islands. These islands are connected pairwise by $n-1$ sea routes, forming a tree.

Each island has enough supplies. Assume that for every day he sails at sea, he must spend $1$ unit of food. A greedy shop owner states that a backpack that can hold $k$ units of food will be sold for $k$ ten-thousand yuan.

PF may order the construction of a bidirectional sea route between any two islands $u$ and $v$ that satisfy both conditions: the travel time between them is not greater than $d$, and on the route from island $v$ to island $u$ there are at least $q$ islands ( excluding $u$ and $v$ ). The travel time of this new route is $\left\lfloor \dfrac{time(u \to v)}{2}\right\rfloor$. Due to budget issues, he can build only one extra route.

Little E can use the official routes ( including the newly added route ) to determine PF's shortest time to each island.

PF will discover Little E's escape at time $t$ and then start the pursuit.

To save money while escaping PF's chase, Little E wants you to write a program to compute the minimum $k$ such that he can successfully escape to at least $l$ islands.

Supplying does not take time. Getting caught on the way still counts as getting caught. Arriving at the same time does not count as being caught.

Replenishing supplies on an island takes no time and can be done infinitely many times, as long as the backpack has enough capacity.

Problem summary:

There are two people $a$ and $b$ and a tree with $n$ nodes. $a$ starts $t$ seconds earlier than $b$. If the travel time between two nodes is not greater than $d$, then $b$ can build a route between these two nodes with travel time $\left\lfloor \dfrac{time(u \to v)}{2}\right\rfloor$. Find a plan such that $a$'s shortest time to at least $l$ nodes is not longer than $b$'s, and on this basis, make the maximum distance between islands as small as possible.

Input Format

The first line contains five integers $n,t,d,l,q$, representing the number of islands, the time when PF discovers the escape, the travel-time limit required to build a route, the minimum number of islands that must be reachable, and the required number of intermediate islands for building a route. Both of their starting points are node $1$.

The next $n-1$ lines each contain four integers $u,v,p_i,e_i$, indicating that there is a route between islands $u$ and $v$. $p_i$ is the time for Little E to travel along this route, and $e_i$ is the time for PF to travel along this route. Routes are bidirectional.

Output Format

If there is a solution, output two lines.

The first line contains an integer $k$, indicating the minimum amount of money needed to escape (unit: ten-thousand yuan).

The second line contains an integer $r$, indicating the number of islands that can be reached when buying a backpack costing $k$ (node $1$ also counts).

If there is no solution, output only no solution.

5 3 20 4 2
1 2 5 5
2 3 5 5
2 4 7 10
1 5 4 1

7
4

5 2 6 3 2
1 2 5 3
2 3 8 6
1 4 8 2
2 5 4 6

5
3

5 0 23 4 1
1 2 21 26
1 3 14 16
3 4 4 5
1 5 19 18

no solution

Hint

[Sample Explanation]

Sample $1$:

For sample $1$, the final reachable nodes are $1,2,4,5$, and the minimum cost is $7$. Since warden PF goes from node $3 \to 5$ along the path $5 \to 1 \to 2 \to 3$, the number of intermediate nodes is $\ge q$, so warden PF can add an edge between nodes $3$ and $5$. If warden PF chooses to add the edge $5 \to 3$, then the time to reach node $3$ is $3 + 1 + \left\lfloor \dfrac{1+5+5}{2}\right\rfloor = 9$. However, Little E's shortest time to node $3$ is $5 + 5 = 10$, which does not satisfy the condition. Therefore, no matter how large $k$ is, node $3$ is unreachable.

[Constraints]

For $100\%$ of the data, $n\le 7.5\times 10^3$, $1\le l\le n$, $0\le t \le 10^8$, $0 \le u_i<v_i \le n$, $1\le p_i,e_i,d\le 10^8$, $0\le q\le 20$.

It is guaranteed that the number of possible plans for the newly built bidirectional route does not exceed $5 \times 10^6$.

Translated by ChatGPT 5