# 1099 : Minimum Spanning Tree

Time Limit: 6 Sec     Memory Limit: 128 Mb     Submitted: 12     Solved: 9

## Description

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)).

## 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 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.

## Output

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

## Sample Input

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

## Sample Output

2
-35

ftiasch