Các sự kiện trong dịp lễ trung thu được diễn ra tại ~N~ địa điểm, có tất cả ~M~ con đường một chiều nối các địa điểm với nhau. 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 bằng xe đạp.

Cuội và Hằng Nga đã đáp con tàu vũ trụ xuống địa điểm ~1~ tại thời điểm ~0~. Cuội thì nóng lòng muốn đạp xe đến địa điểm ~N~ vì ở đây đang diễn ra cuộc thi "Người đẹp đêm rằm". Hằng Nga muốn đi bộ đến địa điểm ~K~ để cùng các em thiếu nhi rước đèn và phá cỗ, sự kiện này bắt đầu tại thời điểm ~X~.

Mặc dù Cuội rất vội nhưng cũng không muốn Hằng Nga bị muộn giờ nên anh ta quyết định cho Hằng Nga đi nhờ đến một địa điểm nào đó (nếu cần) rồi cho Hằng Nga tiếp tục đi bộ đến địa điểm ~K~ còn mình thì tiếp tục đạp xe đế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à Cuội có thể đến được địa điểm ~N~.

Input

• Dòng đầu tiên chứa bốn số nguyên dương ~N, M, K, X~ ~(K \le N; 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 một số nguyên duy nhất là thời gian ít nhất mà Cuội có thể đến được địa điểm ~N~. Nếu không có phương án nào đi theo yêu cầu thì ghi số ~-1~.

Scoring

Sample Input 1

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 1

3

Notes

• Cuội cho Hằng Nga đi nhờ từ địa điểm ~1~ đến địa điểm ~2~ hết ~1~ đơn vị thời gian.

• Hằng Nga đi bộ từ địa điểm ~2~ đến địa điểm ~3~ hết ~3~ đơn vị thời gian. Như vậy Hằng Nga đến địa điểm ~3~ đúng thời điểm ~4~ ~(1 + 3 = 4)~ (Không bị muộn giờ).

• Sau khi cho Hằng Nga xuống địa điểm ~2~, Cuội đạp xe đến địa điểm ~4~ hết ~2~ đơn vị thời gian. Như vậy Cuội đến địa điểm ~4~ hết ~3~ đơn vị thời gian ~(1 + 2 = 3)~.