P6436 "EZEC-1" Prison Break

Due to the warden PF's negligence, the criminal Little E found a chance to break out of prison. However, the uneducated Little E did not know how to keep secrets. PF quickly discovered his plan and started chasing him. Because Little E builds his own boat while warden PF uses an official boat, their performance on each sea route is different, so the travel time may be different. See the input format for details. To avoid going hungry, Little E plans to buy a backpack to carry food.

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.

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**.

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`.

[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] | Test Point ID | $n\le$ | $t\le$ | $p_i,e_i\le$ | $d\le$ | Time Limit | Memory Limit | Feature | | :----------: | :----------: | :----------: | :----------: | :----------: | :-----: | :----------: | :----------: | | $1$ | $10$ | $50$ | $50$ | $50$ | $1s$ | $128M$ | Adding an edge does not affect the answer | | $2$ | $16$ | $50$ | $50$ | $50$ | $1s$ | $128M$ | None | | $3,4$ | $500$ | ${500}$ | ${500}$ | $500$ | $1s$ | $128M$ | Adding an edge does not affect the answer | | $5$ | $500$ | ${500}$ | ${500}$ | ${500}$ | $1s$ | $128M$ | $q = 0$ | | $6,7$ | $500$ | ${500}$ | ${500}$ | ${500}$ | $1s$ | $128M$ | None | | $8$ | $\small{2.5 \times 10^3}$ | $10^8$ | $10^8$ | $10^8$ | $1s$ | $128M$ | Adding an edge does not affect the answer | | $9,10$ | $\small{2.5 \times 10^3}$ | $10^8$ | $10^8$ | $10^8$ | $1s$ | $128M$ | $q = 0$ | | $11 \sim 14$ | $\small{2.5 \times 10^3}$ | $10^8$ | $10^8$ | $10^8$ | $1s$ | $128M$ | None | | $15$ | $\small{2.5 \times 10^3}$ | $10^8$ | $10^8$ | $10^8$ | $1s$ | $256M$ | None | | $16$ | $\small{7.5 \times 10^3}$ | $10^8$ | $10^8$ | $10^8$ | $2s$ | $256M$ | None | | $17$ | $\small{7.5 \times 10^3}$ | $10^8$ | $10^8$ | $10^8$ | $1s$ | $256M$ | None | | $18 \sim 20$ | $\small{7.5 \times 10^3}$ | $10^8$ | $10^8$ | $10^8$ | $3s$ | $512M$ | None | 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