Mạng lưới giao thông của Tý gồm \(N\) thành phố và \(M\) con đường một chiều. Một số con đường hiện đang bị xuống cấp nghiêm trọng và xe cộ không thể lưu thông trừ khi được sửa chữa với chi phí là \(1\) đơn vị vật tư. Các con đường bình thường khác đi qua tốn chi phí \(0\).

Tý muốn đi xe từ thành phố \(S\) đến thành phố \(T\). Do ngân sách có hạn, Tý chỉ được phép lựa chọn lộ trình đi qua tối đa \(X\) con đường cần sửa chữa.

Hãy tìm độ dài ngắn nhất (tính bằng tổng chiều dài địa lý) của con đường đi từ \(S\) đến \(T\) thỏa mãn ràng buộc ngân sách trên.

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

• Dòng đầu chứa sáu số nguyên \(N, M, X, S, T\) (\(1 \le N \le 1000\), \(0 \le M \le 2000\), \(0 \le X \le 10\), \(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, r\) (\(1 \le u, v \le N\), \(1 \le w \le 10^6\), \(r \in \{0, 1\}\)) mô tả con đường một chiều nối \(u\) sang \(v\) có độ dài địa lý \(w\). Nếu \(r = 1\), con đường bị hỏng cần sửa; nếu \(r = 0\), con đường lành lặn.

Định dạng đầu ra

• Một số nguyên duy nhất là tổng độ dài địa lý ngắn nhất. Nếu không thể đi tới thỏa mãn điều kiện, in ra \(-1\).

Ràng buộc

Ví dụ

Input:

4 4 1 1 4
1 2 2 0
2 3 3 1
1 3 10 0
3 4 4 0

Output:

9