给定一棵包含 $N$ 个节点和 $N - 1$ 条边的树 $T$。树的边权每天都会发生变化：在第 $0$ 天，边的权值为 $C_i$，且每天边权会增加 $A_i$。因此，第 $i$ 条边在第 $X$ 天的权值为 $C_i + X \times A_i$。注意，边权可能是负数。

两个节点 $v, w \in V(T)$ 之间的距离定义为路径 $v - w$ 上所有边权之和。注意，树中任意两个节点之间存在唯一路径。树的“直径”定义为任意两个节点之间的最大距离。形式化地，令 $dist(v, w)$ 为树中节点 $v$ 和 $w$ 之间的距离，则 $T$ 的直径定义为 $\max_{i,j \in V(T)} (dist(i, j))$。节点 $i$ 和 $j$ 不必不同。

你将观察这棵树 $D + 1$ 天，从第 $0$ 天到第 $D$ 天。你需要找到一个日期，使得该日期的树直径最小。形式化地，你需要找到一个整数 $x \in [0, D]$，使得区间 $[0, D]$ 内没有任何其他整数对应的直径比它更小。如果存在多个这样的整数，你应该找到其中最小的一个。

输入

第一行包含节点数 $N$ 和观察天数 $D$ ($1 \le N \le 250000, 0 \le D \le 10^6$)。

接下来的 $N - 1$ 行，每行给出四个整数 $S_i, E_i, C_i, A_i$，表示第 $i$ 条边连接两个顶点 $S_i$ 和 $E_i$，其在第 $0$ 天的权值为 $C_i$，且每天增加 $A_i$ ($1 \le S_i, E_i \le N, |C_i| \le 10^8, |A_i| \le 10^3$)。

输出

第一行输出一个整数 $x \in [0, D]$，使得该日期的直径在区间 $[0, D]$ 内最小。如果存在多个这样的整数，输出其中最小的一个。

第二行输出在第 $x$ 天时树的直径。

样例

输入格式 1

3 4
1 2 10 -2
2 3 20 2

输出格式 1

0
30

输入格式 2

3 10
1 2 20 -3
2 3 30 -4

输出格式 2

8
0

输入格式 3

5 5
1 2 20 -3
2 3 10 -3
3 4 22 -2
3 5 26 -3

输出格式 3

5
23

输入格式 4

4 0
1 2 -1 0
2 3 20 0
3 4 -1 0

输出格式 4

0
20