Покос поля

Фермер Джон косит траву.

Ферма представлена двумерной решёткой квадратных ячеек. ФД начинает одной из этих ячеек в момент времени t = 0, косит траву в этой ячейке. Поэтому изначально трава выкошена только в этой ячейке. Дальнейшие действия ФД описываются последовательностью из n предложений. Например, если первое предложение "W 10" то для моментов времени от t = 1 до t = 10 (то есть, следующие 10 единиц времени), ФД будет продвигаться по 1 ячейке на запад, кося траву в каждой ячейке по пути.

ФД медленно косит траву настолько, что она может успеть вырасти ещё прежде чем он закончит процесс. Любая ячейка травы, которую выкосили в момент времени t вырастет снова в момент времени t + x.

В соответствии с последовательностью команд ФД может посещать некоторые ячейки по многу раз, но он не хочет посещать ячейки, в которых трава уже пострижена. То есть, каждый раз, когда он посещает ячейки, его предыдущий визит в эту ячейку должен быть не менее чем на x единиц времени раньше, для того, чтобы выкошенная в этой ячейке трава смогла вновь вырасти.

Определите максимальное значение x, при котором будет выполняться пожелание ФД.

Входные данные

Первая строка ввода содержит n (1 ≤ n ≤ 100). Каждая из оставшихся n строк содержит одно предложение вида "d s", где d это символ направления (N = север, E = восток, S = юг, W = запад), а s (1 ≤ s ≤ 10) - количество шагов, выполненных в этом направлении.

Выходные данные

Пожалуйста, определите максимальное значение x такое, что ФД никогда не ступит на ячейку, где трава ещё не выросла. Если ФД никогда не заходит в ячейку повторно, выведите -1.

Примеры

Примечание

В этом примере в момент времени 17 ФД попадёт в ячейку, в которой он уже был в момент времени 7. Поэтому x должно быть не больше чем 10, иначе к моменту второго посещения не успеет вырасти трава, которую он выкосил при первом посещении. В момент времени 26 он также попадёт в ячейку, в которой он был в момент времени 2. Следовательно, x должно быть не больше чем 24. Из этих двух ограничений выбираем меньшее - 10.