Kelionė autobusu (Lietuva)
Užduotis
Yra N miestų bei M tiesioginių (be tarpinių stotelių) vienos krypties autobusų maršrutų, jungiančių šiuos miestus. Miestai sunumeruoti nuo 1 iki N. Keliautojas, nuliniu laiko momentu esantis pirmame mieste, norėtų atvykti į miestą P, kuriame jis bus pasitiktas laiko momentu T. Jei keliautojas atvyks anksčiau, jam teks laukti.
Kiekvienam autobuso maršrutui i yra žinomi išvykimo bei atvykimo miestai, atitinkamai si ir ti. Taip pat žinomi ir išvykimo bei atvykimo laikai, tačiau tik apytiksliai, t.y. žinoma, kad autobusas išvyksta kažkuriuo laiko momentu iš intervalo [ai, bi] (imtinai), o atvyksta kažkuriuo laiko momentu iš intervalo [ci, di] (imtinai).
Keliautojas nemėgsta laukti, todėl ieško tokio kelionės plano, kuris minimizuotų didžiausią įmanomą laukimo stotyse laiką, ir kartu garantuotų, kad nei į vieną autobusą nebus pavėluota (t.y. persėdant iš autobuso a į autobusą b, vėliausias galimas autobuso a atvykimo laikas neviršys anksčiausio galimo autobuso b išvykimo laiko).
Laukimo laikas skaičiuojamas pagal anksčiausią galimą autobusų atvykimo ir vėliausią galimą autobusų išvykimo laikus.
Parašykite programą, kuri padėtų keliautojui sudaryti jo pageidaujamą kelionės planą.
Pradiniai duomenys
Pirmoje pradinių duomenų bylos TRIP.IN eilutėje įrašyti keturi sveikieji skaičiai N (1  N  50 000), M (1  M  100 000), P (1  P  N) ir T (0  T  1 000 000 000).
Toliau seka M maršrutus apibūdinančių eilučių. Kiekvienoje jų įrašyta po šešis sveikuosius skaičius si, ti, ai, bi, ci, di, kur si ir ti – miestų, iš kurių atitinkamai išvyksta bei atvyksta i-ojo maršruto autobusas, numeriai, o ai, bi, ci, di apibūdina išvykimo bei atvykimo laikus, kaip apibrėžta aukščiau (1  si  N, 1  ti  N, 0  ai  bi < ci  di  1 000 000 000).
Rezultatai
Vienintelėje rezultatų bylos TRIP.OUT eilutėje turi būti įrašytas maksimalus bendras laukimo laikas, sugaištas keliaujant pagal tinkamiausią galimą kelionės planą. Jei neįmanoma garantuoti atvykimo į miestą P ne vėliau negu laiko momentu T, vienintelėje rezultatų bylos eilutėje turi būti įrašytas -1.

Pavyzdžiai
Pradiniai duomenys	Rezultatai	
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
	32
	
Pesimistiškiausias atvejis keliaujant optimaliu kelionės planu aukščiau pateiktame pavyzdyje yra šis:	
Laikas	Veiksmas	
0…1
1…7
7…8
8…9
9…35
35…95
95…98
98…99
99…100	Laukiama mieste 1
Keliaujama maršrutu 3 iš miesto 1 į miestą 1
Laukiama mieste 1
Keliaujama maršrutu 4 iš miesto 1 į miestą 3
Laukiama mieste 3
Keliaujama maršrutu 2 iš miesto 3 į miestą 2
Laukiama mieste 2
Keliaujama maršrutu 5 iš miesto 2 į miestą 2
Laukiama mieste 2	
Bendras laukimo laikas: 1+1+26+3+1=32	

Pradiniai duomenys	Rezultatai	
3 2 2 100
1 3 0 0 49 51
3 2 50 51 100 100
	-1