Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

BUS_ - Tuyến xe buýt

Có N thành phố và M đường 1 chiều  trực tiếp giữa chúng. Các thành phố được đánh số từ 1 đến N, một du khác ở thành phố thứ 1 tại thời điểm 0 và muốn đến thành phố P để dự tiệc với thời gian chính xác là T. Nếu ông ấy đến sớm hơn, ông ấy phải đứng đợi. Với mỗi tuyến xe buýt, ta biêt thành phố khởi đầu U và thành phố đến V, xe sẽ khởi hành ở U trong khoảng thời gian [A..B] và đến V trong khoảng thời gian [C..D] (0 <= A <= B < C <= D). Ông chỉ có thể bắt kịp chuyến xe buýt tiếp theo khi và chỉ khi thời gian đến trễ nhất của chuyến ông đang đi không được lớn hơn thời gian khởi hành sớm nhất của chuyến xe kế tiếp, và lúc này thì thời gian ông cần đợi nhiều nhất sẽ là hiệu của thời gian khởi hành chậm nhất của chuyến xe buýt kế tiếp với thời gian đến sớm nhất của chuyến xe ông đang đi.

Yêu cầu:

Vị du khách này rất ghét việc chờ đợi. Hãy viết chương trình để đưa ra tổng thời gian phải đợi ít nhất của ông.

Input

Dòng đầu chứa 4 số nguyên N , M , P , T

M dòng tiếp , mỗi dòng chứa U[i] , V[i] , A[i] , B[i] , C[i] , D[i]

Output

Một dòng duy nhất ghi tổng thời gian đợi ít nhất của du khách (Nếu ông ấy không thể đến P trong thời gian T thì in ra -1)

Giới hạn

- 1 <= N <= 5 * 10^4

- 1 <= M <= 10^5

- 0 <= T <= 10^9

- 1 <= U[i] , V[i] <= N

- 0 <= A[i] <= B[i] < C[i] <= D[i] <= 10^9

Example

Input:
3 6 2 100
1 3 10 20 30 40
3 2 32 35 95 95
1 1 1 1 7 8
1 3 8 8 9 9
2 2 98 98 99 99
1 2 0 0 99 101
Output: 32
Giải thích:
- Từ 0..1 : Đợi ở thành phố 1
- Từ 1..7 : Dùng tuyến thứ 3 để đi từ thành phố 1 đến thành phố 1
- Từ 7..8 : Đợi ở thành phố 1
- Từ 8..9 : Dùng tuyến thứ 4 để đi từ thành phố 1 đến thành phố 3
- Từ 9..35 : Đợi ở thành phố 3
- Từ 35..95 : Dùng tuyến thứ 2 để đi từ thành phố 3 đến thành phố 2
- Từ 95..98 : Đợi trong thành phố 2
- Từ 98..99 : Dùng tuyến thử 5 để đi từ thành phố 2 đến thành phố 2
- Từ 99..100 : Đợi ở thành phố 2
Tổng thời gian đợi : 1 + 1 + 26 + 3 + 1 = 32

Input:
3 2 2 100
1 3 0 0 49 51
3 2 50 51 100 100
Output: -1

 


Được gửi lên bởi:Tmbao
Ngày:2011-10-02
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:Sưu tầm

hide comments
2018-02-23 15:20:57
SOOOOOO FEN
2018-02-23 15:20:38
NGUYEN HAI NGUYET
2018-02-23 15:20:29
TRINH DINH CAN
2018-02-23 15:20:11
codechup
2011-10-19 16:18:35 kunn
test 1 sao k nhảy lên chuyến thứ 6 luôn???
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.