Có \(N\) trạm tàu điện được xếp thẳng hàng, được đánh số từ 1 đến \(N\). Có \(M\) tuyến tàu điện, mỗi tuyến có đường ray riêng, đánh số từ 1 đến \(M\). Tuyến tàu thứ \(i\) được mô tả bởi 4 số nguyên \(A_i,B_i,C_i,D_i.\)

Tàu chạy hai chiều giữa hai trạm \(A_i\) và \(B_i\) (với \(A_i < B_i\)). Mỗi tuyến phục vụ hai loại tàu:

Tàu thường:

• Dừng ở tất cả các trạm từ \(A_i\) đến \(B_i\) (bao gồm cả hai đầu).

• Chi phí di chuyển từ trạm \(x\) đến trạm \(y\) (với \(A_i ≤ x,y ≤ B_i\)) là \(C_i × |x - y|\).

Tàu tốc hành:

• Chỉ dừng ở \(A_i\) và \(B_i\).

• Chi phí di chuyển giữa hai trạm này (theo cả hai chiều) là \(D_i\).

Để lên tàu, hành khách cần mua vé hành trình với giá \(T\) tại trạm xuất phát. Tuy nhiên, nếu chuyển tuyến tại cùng một trạm, bạn không cần mua vé mới. Nếu rời khỏi trạm và muốn tiếp tục hành trình ở trạm tiếp theo, bạn phải mua vé mới. Ngoài ra, có tuyến xe buýt phủ toàn bộ các trạm. Việc di chuyển từ trạm \(x\) đến trạm \(y\) bằng xe buýt sẽ tốn \(K × |x - y|\).

Yêu cầu: Tìm chi phí ít nhất đi từ trạm \(P\) đến trạm \(Q\) bằng tàu hoặc xe buýt (hoặc kết hợp cả hai).

Input

• Một dòng gồm 6 số nguyên: \(N,M,K,T,P,Q (1≤N,K≤10^5,1≤M≤2×10^5;1≤P,Q≤N;P≠Q). \)

• \(M\) dòng tiếp theo, mỗi dòng chứa 4 số nguyên \(A_i,B_i,C_i,D_i (1≤A_i≤B_i≤N;1≤C_i≤10^5;1≤D_i≤10^9).\)

Output

• In ra chi phí nhỏ nhất cần thiết để đi từ trạm \(P\) đến \(Q\).

Ràng buộc

• Subtask 1: 10% điểm: \(A_i=1;B_i=N.\)

• Subtask 2: 20% điểm:\( N≤1000;M≤5;T=0.\)

• Subtask 3: 20% điểm: \(M≤5. \)

• Subtask 4: 20% điểm: \(T=0.\)

• Subtask 5: 30% điểm: Không có ràng buộc gì thêm.

Sample Input

10 2 10 1 9 5
7 10 10 8
1 6 8 1

Sample Output

38

Giải thích:

• Mua vé 1 tại trạm 9, đi tàu thường đến trạm 10 (chi phí: 10)

• Chuyển sang tàu tốc hành về trạm 7 (miễn phí chuyển tuyến, chi phí: 8)

• Đi xe buýt từ trạm 7 đến 6 (chi phí: 10)

• Mua vé mới tại trạm 6 (1), đi tàu thường đến trạm 5 (chi phí: 8)

Tổng chi phí: 1 + 10 + 8 + 10 + 1 + 8 = 38