「EZEC-1」越狱

由于监狱长 PF 的疏忽，罪犯小 E 找到了机会越狱。 然而，不学无术的小 E 不懂得保密。PF 很快发现了他的计划，并对他展开了追捕。 因为小 E 自己造船，而狱长 PF 坐的是官方的船，所以在每条航道上的表现不一样，通过时间可能不同。具体见输入格式。 为了不饿肚子，小 E 准备买一个包来装食物。

小 E 的逃跑路线可以被看作是在 $n$ 个岛屿上，这些岛屿由 $n-1$ 条航线两两相连。 每个岛上都有足够的补给。**假设他每在海上航行一天，就要花费一个单位的食物**。黑心老板规定，**能装 $k$ 单位的食物的背包将会卖 $k$ 万元**。 PF 可以命令在任意两个**通过时间不超过 $d$**，**并且岛 $v$ 到岛 $u$ 的航线上至少有 $q$ 个岛屿**（**不包括 $u$ 和 $v$**）的岛屿 $u$ 与 $v$ 之间建立一条双向航线，通过这条航线的时间为 $\left\lfloor \dfrac{time(u \to v)}{2}\right\rfloor$。由于经济问题，**他只能建造一条额外的航线**。 小 E 可以根据官方给出的航线（**包括新增的航线**）确认 PF 到每个岛上的**最短时间**。 PF 将会在 $t$ 时发现小 E 逃走并开始追击。 为了节省钱，同时逃脱 PF 的追捕，小 E 想请你帮他编一个程序，计算最小的 $k$，使得他能够顺利逃脱到至少 $l$ 个岛屿。 **补给不需要时间，中途抓住也算抓住，同时到达则不算。** **在岛屿上进行补给不需要时间，可以无限进行补给，只要背包装得下。** 题意概括： 有两个人 $a$，$b$ 和一颗 $n$ 个节点组成的树，$a$ 比 $b$早出发 $t$ 秒。如果两个节点之间通过时间不超过 $d$ 则 $b$ 可以在这两点之间建一条通过时间为 $\left\lfloor \dfrac{time(u \to v)}{2}\right\rfloor$ 的线路，求一个方案使 $a$ 至少到 $l$ 个点的最短时间不比 $b$ 长，并在此基础下要求岛屿之间距离最大值尽量小。

第一行五个整数，$n,t,d,l,q$，表示岛屿的数量，PF 发现的时间，建立航线要求的通过时间范围，至少要到达的岛屿数量，以及建立航线所要求的中间岛屿的数量。他们的出发点均为点 $1$ 。 接下来 $n-1$ 行，每行四个整数 $u,v,p_i,e_i$，表示岛屿 $u$ 和岛屿 $v$ 之间有一条道路。$p_i$ 表示小 E 走这条航线的时间，$e_i$ 表示 PF 走这条航线的时间。**航线为双向** 。

若有解，输出共两行。 第一行一个整数 $k$，表示最小能够逃脱所需要的钱数（单位：万元）。 第二行一个整数 $r$，表示用 $k$ 万元买背包时的能跑到的岛屿数量（ $1$ 号岛也算在内）。 若无解，只需输出 "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

【样例解释】 样例 $1$：  对于样例 $1$，最后能到的点为 $1,2,4,5$，最小花费为 $7$。由于狱长 PF 从点 $3\to 5$ 要经过点为 $5\to1\to2\to3$，满足中间的点数 $\ge q$，故狱长 PF 可以连边点 $3$ 和点 $5$。如果狱长 PF 选择连边 $5\to3$，那么到点 $3$ 的时间为 $3+1+ \left\lfloor \dfrac{1+5+5}{2}\right\rfloor = 9$。而小 E 到点 $3$ 的最短时间为 $5 + 5 = 10$，不满足条件，故无论 $k$ 的大小，点 $3$ 都是不可到达的。 ------------ 【数据范围】 | 测试点编号 | $n\le$ | $t\le$ | $p_i,e_i\le$ | $d\le$ | 时间限制| 空间限制 |特点| | :----------: | :----------: | :----------: | :----------: | :----------: |:-----: | :----------: |:----------: | |$1$ | $10$ | $50$ | $50$ | $50$ |$1s$ | $128M$ |加边操作 不影响答案| |$2$ | $16$ | $50$ | $50$ | $50$ |$1s$ | $128M$ |无| | $3,4$ | $500$ | ${500}$ | ${500}$ |$500$ | $1s$ | $128M$ |加边操作 不影响答案| | $5$ | $500$ | ${500}$ | ${500}$ |${500}$ | $1s$ | $128M$ |$q = 0$| | $6,7$ | $500$ | ${500}$ | ${500}$ |${500}$ | $1s$ | $128M$ |无| | $8$ | $\small{2.5 \times 10^3}$ | $10^8$ | $10^8$ |$10^8$ | $1s$ | $128M$ |加边操作 不影响答案| | $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$ |无| | $15$ | $\small{2.5 \times 10^3}$ | $10^8$ | $10^8$ |$10^8$ | $1s$ | $256M$ |无| | $16$ | $\small{7.5 \times 10^3}$ | $10^8$ | $10^8$ |$10^8$ | $2s$ | $256M$ |无| | $17$ | $\small{7.5 \times 10^3}$ | $10^8$ | $10^8$ |$10^8$ | $1s$ | $256M$ |无| | $18 \sim 20$ | $\small{7.5 \times 10^3}$ | $10^8$ | $10^8$ |$10^8$ | $3s$ |$512M$ |无| 对于 $100 \%$ 的数据，$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$。 **保证可能新建立的双向航线方案数不超过 $5 \times 10^6$**。