Bobo 有一个包含 $n$ 个顶点和 $m$ 条边的无向连通图，其中第 $i$ 条边关联两个参数 $a_i$ 和 $b_i$。

设 $f(x)$ 为当第 $i$ 条边的权重为 $a_i + b_i \cdot x$ 时，该图的最小生成树的边权之和。你的任务是计算 $\min(f(l), f(l+1), \ldots, f(r))$ 的值。

输入格式

输入包含多组测试数据，以文件结束符（EOF）结束。对于每组测试数据：

第一行包含四个整数 $n$、$m$、$l$ 和 $r$，分别表示顶点数、边数以及 $x$ 的取值范围。

接下来的 $m$ 行，第 $i$ 行包含四个整数 $u_i$、$v_i$、$a_i$ 和 $b_i$，表示第 $i$ 条边连接顶点 $u_i$ 和 $v_i$，且该边的参数为 $a_i$ 和 $b_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