Bobo는 $n$개의 정점과 $m$개의 간선으로 이루어진 무방향 연결 그래프를 가지고 있으며, $i$번째 간선에는 두 매개변수 $a_i$와 $b_i$가 주어져 있습니다.

$i$번째 간선의 가중치가 $a_i + b_i \cdot x$일 때 최소 신장 트리의 간선 가중치 합을 $f(x)$라고 합시다. 여러분은 $\min(f(l), f(l+1), \ldots, f(r))$의 값을 계산해야 합니다.

입력

입력은 여러 테스트 케이스로 구성되며, 파일의 끝으로 종료됩니다. 각 테스트 케이스에 대해:

첫 번째 줄에는 네 정수 $n$, $m$, $l$, $r$이 주어지며, 정점의 수, 간선의 수, $x$의 범위를 나타냅니다.

다음 $m$개 줄 중 $i$번째 줄에는 네 정수 $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