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 Odtwarzacz MP3 (mp3)

Odtwarzacz MP3

Limit pamięci: 256 MB

Grzegorz dostał właśnie odtwarzacz MP3, który ma wiele ciekawych funkcjonalności, a wśród nich blokadę klawiatury. Jeśli tylko odtwarzacz jest nieaktywny przez ponad\; sekund, wszystkie jego przyciski zostają zablokowane. Jeśli blokada klawiatury jest włączona, żaden przycisk nie spełnia swojej normalnej funkcji, a gdy tylko jakikolwiek przycisk zostaje naciśnięty, blokada zostaje wyłączona.

Dla przykładu, załóżmy że oraz że klawiatura jest aktualnie zablokowana. Grzegorz nacisnął przycisk , poczekał 3 sekundy, nacisnął przycisk , poczekał 5 sekund, nacisnął , poczekał 6 sekund, a następnie nacisnął . W tym przykładzie jedynie przyciski oraz zadziałały standardowo. Zauważ, że między naciśnięciami przycisków oraz włączyła się blokada klawiatury.

Głośność odtwarzacza MP3 kontroluje się za pomocą przycisków + oraz -, które odpowiednio zwiększają albo zmniejszają poziom głośności o jednostkę. Poziom głośności jest liczbą całkowitą między a . Naciśnięcie przycisku + przy poziomie głośności albo przycisku - przy poziomie głośności nie zmienia aktualnej głośności.

Zadanie

Grzegorz nie zna wartości parametru . Postanowił wyznaczyć tę wartość eksperymentalnie. Zaczynając z zablokowaną klawiaturą, wykonał sekwencję naciśnięć przycisków + i/lub -. Na końcu eksperymentu odczytał z wyświetlacza odtwarzacza ostateczny poziom głośności. Niestety, zapomniał, jaka była głośność odtwarzacza przed rozpoczęciem eksperymentu. Nieznany, początkowy poziom głośności oznaczmy przez , a znany, ostateczny poziom głośności oznaczmy przez .

Masz daną wartość parametru oraz listę naciśnięć przycisków w takiej kolejności, w jakiej naciskał je Grzegorz. Dla każdego naciśnięcia znasz typ naciśniętego przycisku (+ lub -) oraz liczbę sekund od początku eksperymentu do chwili, w której przycisk został naciśnięty. Twoim zadaniem jest wyznaczenie największej możliwej, całkowitej wartości parametru , zgodnej z wynikiem eksperymentu.

Specyfikacja wejścia

Pierwszy wiersz wejścia zawiera trzy liczby całkowite , oraz () pooddzielane pojedynczymi odstępami. Każdy z kolejnych wierszy zawiera opis jednego naciśnięcia w sekwencji: znak "+" lub "-" oraz liczba całkowita (), oznaczająca liczbę sekund od chwili rozpoczęcia eksperymentu. Możesz założyć, że chwile naciśnięć są uporządkowane oraz że wszystkie te chwile są różne (tzn. dla każdego ).

Ograniczenia

Możesz założyć, że oraz .

W testach wartych łącznie 40 punktów zachodzi .

W testach wartych łącznie 70 punktów zachodzi .

Specyfikacja wyjścia

Jeśli może być dowolnie duże, wypisz jeden wiersz zawierający słowo "infinity" (bez cudzysłowów).

W przeciwnym przypadku wypisz jeden wiersz zawierający dwie liczby całkowite oraz oddzielone pojedynczym odstępem.

Wypisane wartości muszą spełniać warunek, że wykonawszy eksperyment z czasem włączenia blokady , począwszy od poziomu głośności , otrzymujemy końcowy poziom głośności . Jeśli jest więcej niż jedno rozwiązanie, wybierz to z nich, które maksymalizuje wartość parametru ; jeśli wciąż jest więcej niż jedno rozwiązanie, wybierz to z nich, które maksymalizuje wartość parametru .

(Zauważ, że zawsze istnieje co najmniej jedno rozwiązanie: jeżeli , to żaden z przycisków nie spełnia swojej normalnej funkcji, więc wystarczy przyjąć ).