题目描述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.

出题Author

ftiasch

来源Source