Zbrodnia na Piccadilly Circus
Limit pamięci: 32 MB
Sherlock Holmes prowadzi śledztwo w sprawie zbrodni na Piccadilly Circus.
Holmes zastanawia się, jaka była maksymalna, a jaka minimalna liczba
osób przebywających równocześnie na miejscu zbrodni w czasie, gdy mogła
zostać ona popełniona. Scotland Yard przeprowadził szczegółowe
śledztwo, przesłuchał wszystkie osoby, które były widziane na miejscu
zbrodni i ustalił, o której godzinie pojawiły sie one na miejscu zbrodni,
a o której je opuściły. Doktor Watson zaofiarował się pomóc przetworzyć
dane zgromadzone przez Scotland Yard i wyznaczyć liczby, które interesują
Sherlocka Holmesa, ma jednak z tym problemy. Pomóż mu!
Zadanie
Napisz program, który:
- wczyta ze standardowego wejścia przedział czasowy, w którym została
popełniona zbrodnia oraz dane zgromadzone przez Scotland Yard,
- wyznaczy minimalną (może to być zero, chociaż dziwne, żeby w czasie
zbrodni nikt nie przebywał w miejscu, w którym się dokonała, ale
właśnie takimi sprawami zajmują się Holmes i Watson)
i maksymalną liczbę osób, które równocześnie
przebywały na miejscu zbrodni w przedziale czasu, gdy mogła ona zostać
popełniona,
- wypisze wyniki na standardowe wyjście.
Wejście
W pierwszym wierszu standardowego wejścia znajdują się dwie liczby
całkowite i , .
Są to, odpowiednio,
najwcześniejsza i najpóźniejsza chwila, kiedy mogła zostać popełniona
zbrodnia. Drugi wiersz standardowego wejścia zawiera jedną liczbę
całkowitą , .
Jest to liczba osób przesłuchanych przez
Scotland Yard. W każdym z kolejnych
wierszy są zapisane po dwie liczby
całkowite - w wierszu zapisane są liczby
i oddzielone
pojedynczym odstępem, . Są to,
odpowiednio, chwila pojawienia się -tej osoby na miejscu
zbrodni i jej
odejścia. Oznacza to, iż -ta
osoba przebywała na miejscu zbrodni przez
cały czas od chwili
do chwili (włącznie).
Wyjście
Twój program powinien wypisać na standardowe wyjście, w pierwszym wierszu
i jedynym wierszu, dwie liczby całkowite oddzielone pojedynczym odstępem:
minimalną i
maksymalną liczbę osób, które były równocześnie na miejscu zbrodni,
w czasie od chwili do chwili (włącznie).
Przykład
Dla danych wejściowych:
5 10
4
1 8
5 8
7 10
8 9
poprawną odpowiedzią jest:
1 4
Autor zadania: Wojciech Guzicki.