题目背景

由于监狱长 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$			$1s$	$128M$	加边操作 不影响答案
$2$	$16$						无
$3,4$	$500$	${500}$		$500$			加边操作 不影响答案
$5$				${500}$			$q = 0$
$6,7$							无
$8$	$\small{2.5 \times 10^3}$	$10^8$					加边操作 不影响答案
$9,10$							$q = 0$
$11 \sim 14$							无
$15$						$256M$
$16$	$\small{7.5 \times 10^3}$				$2s$
$17$					$1s$
$18 \sim 20$					$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$。