Ở Singapore, có \(n\) trạm tàu điện được xếp thẳng hàng, được đánh số từ 1 đến \(n\). Sắp tới Ronaldo sẽ tới Singapore du lịch. 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}\) và \(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:

1. 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}\ \leq x,\ y \leq B_{i}\)) là \(C_{i} \times |x - y|\).

2. 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\ \times \ |x\ - \ y|\). Khách sạn của Ronaldo ở trạm \(P\), anh ấy muốn đ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). Hãy giúp Ronaldo tìm ra chi phí thấp nhất để thực hiện hành trình này.

Dữ liệu vào:

- Một dòng gồm 6 số nguyên: \(n\ m\ K\ T\ P\ Q\) (tách nhau bằng dấu cách)

- \(m\) dòng tiếp theo, mỗi dòng gồm 4 số nguyên \(A_{i}\ B_{i}\ C_{i}\ D_{i}\) (tách nhau bằng dấu cách)

Kết quả:

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

Ràng buộc:

- \(2\ \leq \ n\ \leq \ 100000;\) \(1\ \leq \ m\ \leq \ 200000\ \)

- \(1\ \leq \ K\ \leq \ 100000\)

- \(0\ \leq \ T\ \leq \ 100000\)

- \(1\ \leq \ P,\ Q\ \leq \ n,\ P\ ≠ \ Q\)

- \(1\ \leq \ A_{i} < \ B_{i} \leq \ n\)

- \(1\ \leq \ C_{i}\ \leq \ 100000\)

- \(1\ \leq \ D_{i}\ \leq \ 10^{9}\)

Subtasks:

- 10% điểm: \(A_{i} = \ 1,\ B_{i} = \ n\)

- 20% điểm: \(n \leq 1000,\ M \leq 5,\ T = 0\)

- 20% điểm: \(m\ \leq \ 5\)

- 20% điểm: \(T\ = \ 0\)

- 30% điểm: Không có ràng buộc bổ sung

Ví dụ:

Input	Output
10 2 10 1 9 5 7 10 10 8 1 6 8 1	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