Bobo has an undirected connected graph with n vertices and m edges, where the i-th edge is associated with two parameters ai and bi.
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 ai + bi · x, your task is to calculate the value of min( f(l), f(l+1), ... , f(r) ).
输入描述:
The input consists of several test cases terminated by end-of-file. For each test case:
The first 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 ui, vi, ai and bi, indicating that the i-th edge connects vertices ui and vi and the parameters of the i-th edge. It is guaranteed that the graph is connected.
· 2 ≤ n ≤ 105
· n - 1 ≤ m ≤ 2×105
· 0 ≤ l ≤ r ≤ 106
· 1 ≤ ui, vi ≤ n, ui ≠ vi
· 1 ≤ ai ≤ 106
· -106 ≤ bi ≤ 106
· The sum of n does not exceed 106
· The sum of m does not exceed 2×106
输出描述:
For each test case, print an integer which denotes the result.
示例1
输入
复制
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