Psst... Ruszyły zawody olimpiady informatycznej dla uczniów szkół podstawowych i średnich. Zadania na tych konkursach są bardzo podobne do zadań, które rozwiązujesz, tutaj, na Szkopule.
Zobacz więcej:
- dla uczniów szkół podstawowych: oij.edu.pl/start/
- dla uczniów szkół średnich: oi.edu.pl/l/jak_zaczac/

Zadanie Ograniczenia (ogr)

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:

Autor zadania: Jakub Radoszewski (treść: Marcin Pilipczuk).