Bobo は $n$ 個の頂点と $m$ 本の辺からなる無向連結グラフを持っています。$i$ 番目の辺には 2 つのパラメータ $a_i$ と $b_i$ が与えられています。

$i$ 番目の辺の重みが $a_i + b_i \cdot x$ のとき、最小全域木の辺の重みの総和を $f(x)$ とします。あなたの課題は $\min(f(l), f(l+1), \ldots, f(r))$ の値を求めることです。

入力

入力は複数のテストケースからなり、ファイルの終端で終了します。各テストケースについて：

最初の行には 4 つの整数 $n$、$m$、$l$、$r$ が含まれ、頂点数、辺数、$x$ の範囲を表します。

続く $m$ 行のうち $i$ 行目には 4 つの整数 $u_i$、$v_i$、$a_i$、$b_i$ が含まれ、$i$ 番目の辺が頂点 $u_i$ と $v_i$ を結ぶことと、$i$ 番目の辺のパラメータを表します。グラフが連結であることが保証されます。

• $2 \le n \le 10^5$
• $n - 1 \le m \le 2 \times 10^5$
• $0 \le l \le r \le 10^6$
• $1 \le u_i, v_i \le n$, $u_i \ne v_i$
• $1 \le a_i \le 10^6$
• $-10^6 \le b_i \le 10^6$
• $n$ の総和は $10^6$ を超えません。
• $m$ の総和は $2 \times 10^6$ を超えません。

出力

各テストケースについて、結果を表す整数を出力してください。

入出力例

入力 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

出力 1

2
-35