Hai bạn Quang, Vinh rủ nhau đi chơi. Khu vui chơi gồm ~N~ địa điểm, có ~M~ con đường một chiều nối giữa chúng. Con đường thứ ~i~ (~1 \le i \le M~) đi từ địa điểm ~u_i~ đến địa điểm ~v_i~ hết ~a_i~ đơn vị thời gian nếu đi bộ và hết ~b_i~ đơn vị thời gian nếu đi xe đạp.

Quang và Vinh bắt đầu xuất phát từ địa điểm 1, ở thời điểm 0. Quang muốn đi xe đạp đến địa điểm ~N~. Vinh có kế hoạch đi bộ đến địa điểm ~K~, do có hẹn với bạn nên Vinh cần phải đến đó không muộn hơn thời điểm ~X~.

Quang lo lắng cho Vinh vì nếu đến muộn sẽ khiến bạn của Vinh không vui, nên muốn cho Vinh đi nhờ xe đạp đến một địa điểm nào đó (nếu cần). Vinh cũng không nhất thiết phải cần đi nhờ Quang, còn Quang cũng không nhất thiết phải đưa Vinh đến tận ~K~. Sau khi giúp Vinh để đảm bảo Vinh đến ~K~ không muộn hơn thời điểm ~X~, thì Quang tiếp tục đi xe đạp đến địa điểm ~N~ càng sớm càng tốt.

Yêu cầu: Hãy cho biết thời gian ít nhất mà Quang có thể đến được địa điểm ~N~ mà vẫn giúp được Vinh đến được ~K~ ở thời điểm không muộn hơn ~X~.

Input

• Dòng đầu tiên chứa bốn số nguyên dương ~N, M, K, X~ (~K \le N \le 10^5; X \le 10^9~);
• Dòng thứ ~i~ trong ~M~ dòng tiếp theo chứa bốn số nguyên dương ~u_i, v_i, a_i, b_i~ (~1 \le u_i, v_i \le N; 1 \le b_i \le a_i \le 10^4~).

Output

Ghi ra một số nguyên là thời gian ít nhất mà Quang có thể đến được địa điểm ~N~. Nếu không có phương án nào giúp Vinh đến được ~K~ đúng hẹn thì ghi số ~-1~.

Sample Input

4 6 3 4
1 2 3 1
2 3 3 3
2 4 5 2
1 4 1 1
3 2 1 1
3 4 4 3

Sample Output

3

• Quang cho Vinh đi nhờ từ địa điểm 1 đến địa điểm 2 hết 1 đơn vị thời gian. Vinh đi bộ từ địa điểm 2 đến địa điểm 3 hết 3 đơn vị thời gian. Như vậy Vinh đến địa điểm 3 đúng thời điểm 4 (~1 + 3 = 4~) và không bị muộn giờ.
• Sau khi cho Vinh xuống địa điểm 2, Quang đi xe đạp đến địa điểm 4 hết 2 đơn vị thời gian. Như vậy Quang đến địa điểm 4 hết ~1 + 2 = 3~ đơn vị thời gian.

Ràng buộc

• Subtask 1 (30% số điểm): ~N, M \le 1000~;
• Subtask 2 (40% số điểm): ~N, M \le 10^5; K = N~;
• Subtask 3 (30% số điểm): ~1000 < N, M \le 10^5~.