Problem description

Back
Show PDF
Budowa pasa
(bud)
Limit pamięci: 256 MB
Limit czasu: 0.50 s

Ryszard miał 35 dni na budowę lotniska. Zaniedbał jednak to zadanie, a na domiar złego dopiero teraz wrócił do domu. Na wykonanie tego zadania zostało mu niewiele czasu, więc będziesz musiał mu pomóc.

Teren inwestycyjny to nieskończona siatka kwadratowych pól jednostkowych. W chwili t = 0 Ryszard znajduje się na jednym z pól i rozpoczyna na nim układanie pasa startowego. Jest to jedyne pole lotniska z położonym pasem w tej chwili. Dalsze prace opisuje ciąg poleceń. Przykładowo polecenie W 10 oznacza, że przez następnych 10 jednostek czasu Ryszard będzie przemieszczał się o jedno pole na zachód w każdej jednostce czasu, układając pas na odwiedzanych polach.

Niestety Ryszard jest z natury bardzo skąpy i używa najtańszych materiałów budowlanych. Z tego powodu zbudowany przez niego pas nie jest zbyt wytrzymały – każdy fragment nawierzchni ułożony w chwili t rozpada się i znika dokładnie po x jednostkach czasu, czyli w chwili t + x.

Podczas budowy Ryszard może odwiedzać to samo pole wielokrotnie. Twierdzi jednak, że nigdy nie marnowałby materiałów na pole, na którym nawierzchnia jest już ułożona, bo to się nie opłaca. Innymi słowy, za każdym razem, gdy wracał na dane pole, poprzednio ułożona tam nawierzchnia musiała już zdążyć się rozpaść (ostatnio był na tym polu co najmniej x jednostek czasu temu).

Wyznacz największą możliwą wartość x, dla której Ryszard nie jest kłamcą.

Wejście

W pierwszym wierszu wejścia znajduje się liczba N, oznaczająco ilość instrukcji według, których Ryszard będzie się poruszał. W każdym z kolejnych N wierszy znajduje się kierunek, w którym Ryszard będzie się poruszał (N - góra, E - prawo, S - dół, W - lewo), oraz liczba A, czyli ile kroków wykona w danym kierunku.

Wyjście

W jedynym wierszu wyjścia powinna się znaleźć maksymalna liczba x, dla której Ryszard spełni swoje założenia o wracaniu na pola. Jeśli Ryszard nigdy nie wróci na żadne pole, na którym już był to wypisz  − 1.

Ograniczenia

1 ≤ N ≤ 100, 1 ≤ A ≤ 10.

Podzadanie

Podzadanie Warunki Punkty
1 Ryszard porusza się tylko w górę lub w prawo 6
2 N = 2 10
3 Ryszard nigdy nie jest na lewo
ani nigdy nie jest niżej niż jego pole początkowe 20
4 Brak dodatkowych ograniczeń 64

Przykład

Wejście Wyjście Wyjaśnienie 
6
N 10
E 2
S 3
W 4
S 5
E 8
 
10

Ryszard wejdzie na pole w chwili t = 26, na którym już był w chwili t = 2, a więc x jest co najwyżej 24. Wejdzie również na pole w chwili t = 17, na którym już był w chwili t = 7, czyli x jest co najwyżej 10. Jako że to drugie ograniczenie jest mocniejsze to odpowiedź to 10.
Wejście Wyjście 
5
N 2
W 10
S 3
E 2
N 1
 
-1
Wejście Wyjście 
7
E 9
S 5
W 7
N 3
N 4
W 2
S 1
 
24