ROBISON sau khi bị lạc trên đảo hoang, anh ta đã tự đóng một con thuyền bằng những tấm gỗ dày ~ k ~ cm. Vùng biển anh ta sống có ~ n ~ hòn đảo được đánh số từ 1 đến ~ n ~. Có ~ m ~ tuyến đường biển giữa các hòn đảo này, tuyến thứ ~ i ~ cho phép thuyền đi lại giữa hai đảo ~ a_i ~ và ~ b_i ~ ~ (1 ≤ a_i, b_i ≤ n ) ~ trong thời gian ~ t_i ~. Bên cạnh đó, tuyến đường ~ i ~ còn có những hòn đá ngầm mà khi thuyền đi qua nó sẽ bào mòn vỏ thuyền ~ h_i ~ cm. Có thể có nhiều tuyến đường biển giữa mỗi cặp hòn đảo.

Hôm này ROBISON muốn khám phá hòn đảo ~ B ~ (anh ta sống ở đảo ~ A ~) ~ ( 1 ≤ A, B ≤ n ) ~ và anh ấy sẽ chèo thuyền đi theo một dãy các tuyến đường biển liên tiếp nào đó. Tất nhiên là không được để vỏ thuyền bị đá ngầm cào thủng (nghĩa là tổng các giá trị ~ h_i ~ trên các tuyến đường mà thuyền đi qua phải nhỏ hơn ~ k ~ ) và tổng thời gian đi là nhỏ nhất. Hãy giúp ROBISON tìm một tuyến đường như vậy hoặc cho biết là không có tuyến đường phù hợp.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên ~ k, n ~ và ~ m ~ ~ (1 ≤ k ≤ 200, 2 ≤ n ≤ 2000, 1 ≤ m ≤ 10000) ~.
• Dòng thứ ~ i ~ trong ~ m ~ dòng tiếp theo chứa bốn số nguyên ~ a_i ~, ~ b_i ~, ~ t_i ~ và ~ h_i ~ ~ (1 ≤ a_i ≠ b_i ≤ n, 1 ≤ t_i ≤ 10^5, 0 ≤ h_i ≤ 200) ~ các nhau bởi dấu cách.
• Dòng cuối cùng chứa hai số nguyên ~ A ~ và ~ B ~ ~ (1 ≤ A ≠ B ≤ n) ~.

Kết quả

In ra một số nguyên là tổng thời gian nhỏ nhất để ROBISON đi từ ~ A ~ đến ~ B ~ mà không bị thủng thuyền. Nếu không có cách đi thì in ra số ~ -1 ~.

Ràng buộc

• Có 20% test ứng với ~ k = 1, n ≤ 200 ~
• Có 20% test ứng với ~ k = 1, n ≤ 2000 ~.

Ví dụ:

Input 1

10 4 7
1 2 4 4
1 3 7 2
3 1 8 1
3 2 2 2
4 2 1 6
3 4 1 1
1 4 6 12
1 4 

Output 1

7 

Input 2

3 3 3
1 2 5 1
3 2 8 2
1 3 1 3
1 3 

Output 2

-1