Bobo tiene un grafo no dirigido y conexo con $n$ vértices y $m$ aristas, en el que la $i$-ésima arista tiene asociados dos parámetros $a_i$ y $b_i$.

Sea $f(x)$ la suma de los pesos de las aristas del árbol de expansión mínimo cuando el peso de la $i$-ésima arista es $a_i + b_i \cdot x$. Tu tarea es calcular el valor de $\min(f(l), f(l+1), \ldots, f(r))$.

Entrada

La entrada consta de varios casos de prueba y termina al llegar al final del archivo. Para cada caso de prueba:

La primera línea contiene cuatro enteros $n$, $m$, $l$ y $r$, que indican el número de vértices, el número de aristas y el intervalo de $x$.

La $i$-ésima de las siguientes $m$ líneas contiene cuatro enteros $u_i$, $v_i$, $a_i$ y $b_i$, que indican que la $i$-ésima arista conecta los vértices $u_i$ y $v_i$, y los parámetros de la $i$-ésima arista. Se garantiza que el grafo es conexo.

• $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$
• La suma de $n$ no supera $10^6$.
• La suma de $m$ no supera $2 \times 10^6$.

Salida

Para cada caso de prueba, imprime un entero que represente el resultado.

Ejemplos

Entrada 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

Salida 1

2
-35