잔디 깎기

존 농부는 농장 관리의 거의 모든 면에서 믿음직하지만, 잔디 깎기만은 제때 짜임새 있게 해내지 못한다.

농장은 정사각형 단위 칸으로 이루어진 큰 2차원 격자다. 시각 $t = 0$에 존은 이 중 한 칸에서 출발하면서 그 칸의 잔디를 깎는다. 그래서 처음에 잔디가 깎여 있는 칸은 그 한 칸뿐이다. 이후의 이동은 $N$개의 명령으로 주어진다. 예를 들어 첫 명령이 "W 10"이면 시각 $t = 1$부터 $t = 10$까지, 즉 다음 10단위 시간 동안 존은 서쪽으로 한 칸씩 옮겨 가며 지나는 칸의 잔디를 깎는다. 이 명령을 마치면 시각 $t = 10$에 출발 지점에서 서쪽으로 10칸 떨어진 칸에 서 있고, 지나온 모든 칸의 잔디가 깎여 있다.

존의 작업이 워낙 느려서 깎아 둔 잔디 중 일부는 작업이 끝나기 전에 다시 자란다. 시각 $t$에 깎인 잔디는 시각 $t + x$에 다시 자란다.

존은 같은 칸을 여러 번 지날 수도 있지만, 잔디가 아직 깎인 채로 남아 있는 칸은 한 번도 밟지 않았다고 말한다. 즉 어떤 칸을 밟을 때마다 그 칸을 직전에 밟은 시각이 적어도 $x$단위 시간 앞서 있어서 잔디가 이미 다시 자라 있었다.

존의 말이 성립하도록 하는 $x$의 최댓값을 구하라.

첫째 줄에 $N$이 주어진다 ($1 \le N \le 100$). 이어지는 $N$개의 줄에는 명령이 한 줄에 하나씩 "D S" 형태로 주어진다. D는 방향을 나타내는 문자로 N은 북쪽, E는 동쪽, S는 남쪽, W는 서쪽을 뜻한다. S는 그 방향으로 움직이는 칸 수이며 $1 \le S \le 10$이다.

존이 잔디가 깎여 있는 칸을 한 번도 밟지 않게 되는 $x$의 최댓값을 한 줄에 출력한다. 존이 어떤 칸도 두 번 이상 밟지 않으면 -1을 출력한다.

예제에서 존은 시각 7에 밟았던 칸을 시각 17에 다시 밟는다. 그래서 $x$는 10 이하여야 한다. 그렇지 않으면 첫 방문 때 깎인 잔디가 아직 자라지 않은 상태다. 시각 2에 밟은 칸도 시각 26에 다시 밟으므로 $x$는 24 이하이기도 하다. 앞의 조건이 더 강하므로 $x$의 최댓값은 10이다.