Ograniczenia
Limit pamięci: 64 MB
Piotruś wraca ze Szwajcarii do Polski na finał Potyczek. Planuje
jechać samochodem. Główną część jego podróży będzie jazda nową,
wspaniałą polską autostradą . Planuje wjechać na autostradę
na -tym kilometrze i opuścić ją na -tym kilometrze ().
Samochód Piotrka może jechać z maksymalną prędkością
kilometrów na godzinę.
Piotrek bardzo lubi szybko jeździć. Jeśli jedzie kilometrów z
prędkością , jego zadowolenie wzrasta o . Chce on
przejechać całą trasę po autostradzie tak, by być jak
najbardziej zadowolonym na koniec podróży.
Niestety, na autostradzie jest ograniczeń prędkości.
-te ograniczenie prędkości obowiązuje od kilometra aż do
kilometra autostrady. Na tym odcinku nie wolno jechać szybciej
niż kilometrów na godzinę. Na jednym odcinku autostrady może
obowiązywać kilka ograniczeń prędkości, należy wówczas przestrzegać
wszystkie ograniczenia.
Piotruś ma znajomych. Znajomi zobowiązali się cichaczem usunąć jedno
ograniczenie prędkości. Piotruś się teraz zastanawia, które
ograniczenie usunąć, by być jak najbardziej szczęśliwym na koniec
podróży. Pomóż mu!
Zadanie
Napisz program, który:
- wczyta ze standardowego wejścia opis ograniczeń prędkości,
maksymalną prędkość samochodu i opisy miejsc, gdzie Piotruś
wjeżdża i wyjeżdża z autostrady,
- wyznaczy które ograniczenie znajomi Piotrka powinni
usunąć,
- wypisze wynik na standardowe wyjście.
Wejście
Pierwszy wiersz wejścia zawiera cztery liczby całkowite , ,
, : , ,
. Każdy z kolejnych wierszy zawiera opis jednego
ograniczenia. Wiersz o numerze zawiera trzy liczby całkowite
i , oznaczające
kilometr początka i końca ograniczenia oraz maksymalną prędkość
obowiązującą na tym odcinku.
Wyjście
Pierwszy i jedyny wiersz wyjścia powinien zawierać jedną liczbę
całkowitą, oznaczającą numer ograniczenia, które należy usunąć.
Ograniczenia ponumerowane są liczbami naturalnymi od do w
kolejności jak w danych wejściowych. Jeśli dla kilku ograniczeń
ich usunięcie tak samo wpłynie na zadowolenie Piotrka, należy
wypisać numer ograniczenia występującego najwcześciej w danych
wejściowych.
Przykład
Dla danych wejściowych:
2 10 20 200
10 15 80
10 13 40
poprawną odpowiedzią jest:
1
Autor zadania: Jakub Radoszewski (treść: Marcin Pilipczuk).