Фермер Джон косит траву.
Ферма представлена двумерной решёткой квадратных ячеек. AL начинает одной из этих
ячеек в момент времени \(t = 0\), косит траву в этой ячейке. Поэтому изначально трава
выкошена только в этой ячейке. Дальнейшие действия ФД описываются последовательностью
из \(N\) предложений. Например, если первое предложение "W 10" то для моментов
времени от \(t = 1\) до \(t = 10\) (то есть, следующие 10 единиц времени), ФД будет
продвигаться по 1 ячейке на запад, кося траву в каждой ячейке по пути.
ФД медленно косит траву настолько, что она может успеть вырасти ещё прежде чем
он закончит процесс. Любая ячейка травы, которую выкосили в момент времени \(t\)
вырастет снова в момент времени \(t + x\).
В соответствии с последовательностью команд ФД может посещать некоторые ячейки
по многу раз, но он не хочет посещать ячейки, в которых трава уже пострижена.
То есть, каждый раз, когда он посещает ячейки, его предыдущий визит в эту ячейку
должен быть не менее чем на \(x\) единиц времени раньше, для того, чтобы выкошенная
в этой ячейке трава смогла вновь вырасти.
Пожалуйста, определите максимальное значение \(x\), при котором будет выполняться
пожелание ФД.
ФОРМАТ ВВОДА (файл mowing.in):
Первая строка ввода содержит \(N\) (\(1 \leq N \leq 100\)). Каждая из оставшихся \(N\)
строк содержит одно предложение вида 'D S', где D это символ направления,
(N=север, E=восток, S=юг, W=запад), а S - количество шагов, выполненных в этом
направлении (\(1 \leq S \leq 10\)).
ФОРМАТ ВВОДА (файл mowing.out):
Пожалуйста, определите максимальное значение \(x\) такое, что ФД никогда не ступит
на ячейку, где трава ещё не выросла. Если ФД никогда не заходит в ячейку повторно,
выведите -1.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
N 10
E 2
S 3
W 4
S 5
E 8
|
10
|