An thám hiểm một hang động gồm \(N\) khoang và \(M\) lối đi một chiều nối giữa chúng. Mỗi lối đi từ \(u\) sang \(v\) có chi phí di chuyển \(w\) và độ gập ghềnh \(h\) (nhận giá trị \(0\) là bằng phẳng, \(1\) là hiểm trở).

An xuất phát từ khoang \(S\) và muốn tới khoang \(T\) sao cho tổng số lối đi hiểm trở đi qua trên hành trình không vượt quá \(C\). Hãy tìm tổng chi phí di chuyển tối thiểu thỏa mãn yêu cầu này.

Định dạng đầu vào

• Dòng đầu chứa năm số nguyên \(N\), \(M\), \(C\), \(S\), \(T\) (\(1 \le N \le 500\), \(0 \le M \le 1000\), \(0 \le C \le 50\), \(1 \le S, T \le N\)).
• \(M\) dòng tiếp theo, mỗi dòng chứa bốn số nguyên \(u\), \(v\), \(w\), \(h\) (\(1 \le u, v \le N\), \(-100 \le w \le 1000\), \(h \in \{0, 1\}\)).

Định dạng đầu ra

• In ra chi phí tối thiểu thỏa mãn điều kiện. Nếu không có hành trình nào hợp lệ, in ra impossible.

Ràng buộc

• Subtask 1 (40% số điểm): \(N \le 50\), \(M \le 100\), \(C \le 10\).
• Subtask 2 (60% số điểm): Không có ràng buộc gì thêm.

Ví dụ

Input:

3 3 1 1 3
1 2 5 1
2 3 5 1
1 3 15 0

Output:

15

Giải thích: Đường đi \(1 \to 2 \to 3\) có tổng chi phí là \(10\) nhưng đi qua \(2\) cạnh hiểm trở (vượt quá giới hạn \(C=1\)). Đường đi duy nhất hợp lệ là \(1 \to 3\) có chi phí \(15\) và đi qua \(0\) cạnh hiểm trở.