El Granjero Juan es bastante confiable en todos los aspectos de manejar su granja, excepto en una: él es terrible podando el pasto de una manera lógica o que use bien el tiempo.

La granja es una cuadrícula bidimensional de celdas unidades cuadradas. GJ comienza en una de estas celdas en el tiempo ~t=0~, podando el pasto en esta celda de tal manera que es inicialmente la única celda cuyo pasto está cortado. El patrón faltante de GJ está descrito por una secuencia de ~N~ sentencias. Por ejemplo, si la primera sentencia es "~W~ ~10~", entonces para los tiempos desde ~t=1~ hasta ~t=10~ (esto es las siguientes ~10~ unidades de tiempo), GJ parará en cada celda hacia el oeste, podando el pasto en su camino. Después de terminar esta secuencia de pasos, él terminará ~10~ celdas a su oeste en el tiempo ~t=10~, habiendo podado el pasto en cada celda a lo largo del camino.

Es tan lento el progreso de GJ que parte del poste que él poda podría crecer nuevamente antes que él finalice con todo su podado. Cualquier sección que sea cortada en el tiempo ~t~ reaparecerá en el tiempo ~t+x~.

El patrón de podado de GJ podría hacer que él re-visitara la misma celda varias veces, pero él remarca que él nunca llegará a una celda que ya haya sido podada. Esto es, cada vez que él visita una celda, su visita más reciente a esa misma celda debe haber sido hecha ~x~ unidades de tiempo más temprano, para que el pasto haya crecido de vuelta.

Por favor, determine el valor máximo posible de ~x~ de tal manera que la observación de GJ permanezca válida.

Entrada

La primera línea de la entrada contiene ~N~ ~(1 \leq N \leq 100)~. Cada una de las siguientes ~N~ líneas contiene una sola sentencia y es de la forma '~D~ ~S~', donde ~D~ es un caracter describiendo una dirección (N=norte, E=este, S=sur, W=oeste) y ~S~ es el número de pasos tomado en esa dirección ~(1 \leq S \leq 10)~.

Salida

Por favor determine el valor máximo de ~x~ tal que GJ nunca pise una celda con pasto podado. Si GJ nunca visita ninguna celda más de una vez, por favor, dé como salida ~-1~.

Ejemplo de Entrada

6
N 10
E 2
S 3
W 4
S 5
E 8

Ejemplo de Salida

10

En este ejemplo, GJ pisa una celda en el tiempo ~17~ en la cual había estado más temprano en el tiempo ~7~; por lo tanto ~x~ debe ser a lo más ~10~ o en otro caso el pasto desde su primera visita no habría crecido de vuelta. También pisa una celda en el tiempo ~26~ que también visitó en el tiempo ~2~; por lo tanto ~x~ de ser a lo más ~24~. Desde que la primera de esas dos restricciones es más apretada, vemos que ~x~ puede ser a lo más ~10~.