1099 : Minimum Spanning Tree

Description

Bobo has an undirected connected graph with n vertices and m edges, where the i-th edge is associated with two parameters a_i and b_i.

Let f(x) be the sum of weights of the edges in the minimum spanning tree when the weight of the i-th edge is a_i + b_i ⋅ x, your task is to calculate the value of min (f(l), f(l + 1), …, f(r)).

Input

The input consists of several test cases terminated by end-of-file. For each test case:

The first line contains four integers n, m, l and r, indicating the number of vertices, the number edges and the range of x.

For the next m lines, the i-th line contains four integers u_i, v_i, a_i and b_i , indicating that the i-th edge connects vertices u_i and v_i and the parameters of the i-th edge. It is guaranteed that the graph is connected.

• 2 ≤ n ≤ 10⁵
• n − 1 ≤ m ≤ 2 × 10⁵
• 0 ≤ l ≤ r ≤ 10⁶
• 1 ≤ u_i, v_i ≤ n, u_i ≠ v_i
• 1 ≤ a_i ≤ 10⁶
•  − 10⁶ ≤ b_i ≤ 10⁶
• The sum of n does not exceed 10⁶.
• The sum of m does not exceed 2 × 10⁶.

Output

For each test case, print an integer which denotes the result.

Sample

5 6 1 5
1 2 3 1
2 3 5 -1
3 4 1 2
4 5 1 -1
5 1 5 3
2 4 3 -1
5 6 1 5
1 2 1 1
2 3 1 2
3 4 1 -10
3 4 2 10
5 1 3 10
2 4 5 -10

2
-35

Hint

Source

Author

ftiasch