You are given a tree $T$ with $N$ nodes and $N - 1$ edges. The tree has a cost associated with its edges, which changes every day: In day $0$, the edge has cost $C_i$, and the cost of edges changes by $A_i$ each day. Thus, the $i$-th edge will have cost $C_i + X \times A_i$ on day $X$. Note that the weight of edges might be negative.

The distance between two nodes $v, w \in V(T)$ is defined as the sum of the costs of the edges on the path between $v$ and $w$. Note that there exists exactly one path between every two nodes in a tree. The "diameter" of the tree is defined as the maximum distance between any two nodes. Formally, let $dist(v, w)$ be the distance between nodes $v$ and $w$ in $T$, then the diameter of $T$ is defined as $\max_{i,j \in V(T)} (dist(i, j))$. Nodes $i$ and $j$ do not have to be distinct.

You will observe the tree for $D + 1$ days, starting from day $0$ until day $D$. You want to find a day which minimizes the diameter—formally, you need to find an integer $x \in [0, D]$ such that no other integer in $[0, D]$ yields a smaller diameter. If there is more than one such integer, you should find the smallest such integer.

Input

The first line contains the number of nodes $N$ and the number of observing days $D$ ($1 \le N \le 250000$, $0 \le D \le 10^6$).

In the next $N - 1$ lines, four integers $S_i, E_i, C_i, A_i$ are given, indicating that edge $i$ connects two vertices $S_i$ and $E_i$, has cost $C_i$ on day $0$, and changes by $A_i$ every day ($1 \le S_i, E_i \le N$, $|C_i| \le 10^8$, $|A_i| \le 10^3$).

Output

In the first line, print the integer $x \in [0, D]$ that minimizes the diameter in the interval $[0, D]$. If there is more than one such integer, you should find the smallest such integer.

In the next line, print the diameter of the tree on day $x$, where $x$ is the day you found in the first line.

Examples

Input 1

3 4
1 2 10 -2
2 3 20 2

Output 1

0
30

Input 2

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

Output 2

8
0

Input 3

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

Output 3

5
23

Input 4

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

Output 4

0
20