Có ~N~ địa điểm và ~M~ con đường một chiều.

Đường thứ i từ ~u_i~ đến ~v_i~ có thời gian đi bộ ~a_i~ và thời gian đi xe đạp ~b_i~ (luôn nhỏ hơn hoặc bằng a_i)

Quang và Vinh xuất phát từ địa điểm ~1~.

Vinh muốn đến địa điểm ~K~ không muộn hơn thời điểm ~X~.

Quang có thể:

Đạp xe từ đầu đến cuối (đi xe ở mọi chặng)

Hoặc tại một địa điểm duy nhất nào đó, Quang có thể chở Vinh đi xe đạp (dùng thời gian ~b_i~ thay cho ~a_i~) để giúp Vinh đến ~K~ kịp giờ ~X~.

Sau khi giúp Vinh xong, 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: Tìm thời gian nhỏ nhất để Quang đến được địa điểm ~N~ mà vẫn giúp được Vinh đến ~K~ không muộn hơn ~X~. Nếu không thể giúp được Vinh đúng hạn, in ~-1~.

Input

Dòng 1: Chứa 4 số nguyên ~N, M, K, X~ (~K ≤ N ≤ 10^5, X ≤ 10^9~)

M dòng tiếp: ~u_i, v_i, a_i, b_i~ (~1 ≤ u_i, v_i ≤ N, 1 ≤ b_i ≤ a_i ≤ 10^4~)

Output

Một số nguyên: thời gian nhỏ nhất để Quang đến N và vẫn giúp Vinh đến ~K~ kịp giờ ~X~.

Nếu không có phương án hợp lệ, in ~-1~.

Test mẫy

Input

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

Output

3

Scoring

Subtask 1 (~30\%~): ~N, M \le 1000~

Subtask 2 (~40\%~): ~N, M \le 10^5, K = N~

Subtask 3(~30\%~): ~1000 < N, M \le 10^5~