该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

Steve与Alice是两个Mineeraf玩家，一天他们找到了一张有趣的空岛地图，决定在这张地图上玩一个有趣的追杀游戏

首先讲一下游戏的规则

Steve是追捕者，而Alice是逃跑者

在这张地图上有n个空岛，这n个点空岛构成一棵树，即由n - 1条无向路径构成

为了使游戏更加的好玩，他们约定如下：

1. Steve与Alice都从1号出发，但追捕者Steve比逃跑者Alice晚出发t s

2. 对于第i条路径，Alice通过的时间为ai，而Steve通过的时间为b；

3. 每个空岛上拥有一枚珍贵的钻石（包括1号点）

4. 在整场追杀游戏中，Alice的获胜条件为成功拿到枚钻石（拿取钻石不需要耗费时间），而Steve的获胜条件就是在Alice得到枚钻石前抓捕到她。整场游戏分为很多轮，在Alice被抓住前，她可以在任意时刻选择结束本轮游戏，一轮游戏结束后，Alice在本轮拿到的钻石不会清空，而被拿过钻石的空岛也不会再刷新钻石，Alice与Steve将重新回到1号空岛开始下一轮游戏，Steve需要再次等待t s，再开始追捕Alice。当然，若游戏陷入僵局，即Alice无论如何都会不到新的钻石，游戏也将结束，根据Alice得到的钻石数判定胜负

5. Steve出于绅士风度，时刻牢记女士优先，所以当二人同时到达一个空岛时，Steve会放走Alice，不会对她抓捕

6. Steve在游戏开始前，仅可以在两个空岛U与V间搭建一条只有他自己能经过的路经，为了游戏平衡，搭建路径必须满足以下两个条件

   (1). 在这两个空岛U与V的路经上至少要存在7个空岛（不包含U与V）

   (2). 对于Steve，从空岛U到达空岛V的最短时间不能超过d 而Steve通过这条人造路径所花费的时间为[ \frac{w}{2} ] （向下取整w/2）

Steve很聪明，他会想尽办法抓住Alice，所以当Alice有可能在某一个空岛上被抓住时，为了稳妥起见，Alice不会前往这个空岛

但Alice非常愿意得游戏，于是她来请教你，首先你要告诉她，她到底能不能获得到枚钻石并取得游戏的胜利。

如果可以，由于Alice在游戏开始前向Steve放话："我只需要走对于我而言所用时间不超过k的路经就能赢你！"请你帮她找出最小的k为多少，并且在此基础上，求出她最多能拿到的钻石数量r

（嘘：偷偷告诉你，Alice是不知道Steve会建哪一条边的oh。）

输入格式

第一行5个整数，分别为空岛数量n，Steve比Alice晚出发的时间t，人工搭路条件中的d，Alice取得胜利需要的钻石数量l，人工搭路条件中的q

接下来n - 1行，每行四个整数u, v, a, b，表示空岛u和空岛v之间有一条路径。a表示Alice走这条路径的时间，b表示Steve走这条路径的时间。

输出格式

若Alice能获胜，输出共两行。 第一行一个整数k，含义如题， 第二行一个整数r，表示在只走不大于k的路径的前提下，所能获取到的最多的钻石数量

若无解，只需输出"no solution"（引号不需要输出）。

样例

输入样例1

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

输出样例1

7
4

输入样例2

4 0 100 3 0
1 2 1 100
1 3 1 100
1 4 1 100

输出样例2

1
4

输入样例3

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

输出样例3

no solution

数据范围与提示

本题采用捆绑测试

对于100%的数据， 0 < n ≤ 7500, 1 ≤ l ≤ n, 0 ≤ t ≤ 10^8, 0 ≤ u_i < v_i ≤ n, 1 ≤ a_i, b_i, d ≤ 10^8, 0 ≤ q ≤ 20.